[數學][Phi]1514 - Problem D. 橫掃射擊場

Shaymin

原題：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，好像有線性作法，徵詢一下

遊客，本帖隱藏的內容需要積分高於 215 才可瀏覽，您當前積分為 0