竹園論壇

標題: [數學][Phi]1514 - Problem D. 橫掃射擊場 [打印本頁]

作者: Shaymin 時間: 2015-2-12 10:35
標題: [數學][Phi]1514 - Problem D. 橫掃射擊場
原題：http://tioj.ck.tp.edu.tw/problems/1514
AC：http://tioj.ck.tp.edu.tw/submissions/9114

就是要求：[tex]%5Cleft%20%7C%20S%20%5Cright%20%7C%2CS%3D%5C%7B%20%28a%2Cb%29%5Cmid%20%5Cforall%20a%2Cb%5Cin%20%5Cmathbb%7BN%7D%20%5Cwedge%20a%2Cb%5Cleq%20n%20%5Cwedge%20gcd%20%28a%2Cb%29%3D1%5C%7D[/tex] (就是有多少對互值拉)

導出來的通式：[tex]1+2%5Csum_%7Bi%3D0%7D%5E%7Bn%7D%20%5Cphi%28i%29[/tex]

只會用[tex]O(nlogn)[/tex]建phi表ZZZ，好像有線性作法，徵詢一下

歡迎光臨竹園論壇 (http://forum.tfcis.org/)