tioj 1514 橫掃射擊場

看到小包寫我才去寫的，這真的是一題好題
我終於把歐拉跟費馬這兩個人做的一大堆事中的一小部分弄懂了

PHI函數：

定義：phi(n)=1~n與n互質的個數
特性：
1. p為質數，phi(p)=p-1;
pf: 1~n-1都跟p互質

2. p為質數，phi(p^k)=p^(k-1) * (p-1);
pf:  有p^(k-1)個數是p的倍數，但其餘的(p-1)*p^(k-1)個數都不是，所以都跟他互質

3. p為質數，phi(p^(k+1))=phi(p^k)*p
pf: 因，phi(p^k)=p^(k-1)*(p-1); 且，phi(p^(k+1))=p^k*(p-1);  故，phi(p^(k+1))=phi(p^k)*p;

4. 若(a,b)=1，phi(a*b)=phi(a)*phi(b);
pf: 好難證...

5. 若x=p1^k1*p2^k2*...，則 phi(n)=n[ (p1-1)*(p2-1)*(p3-1)*... ] / [ p1*p2*p3*... ]
pf:用三跟四，就可以容易的證出來，但有點長...

定理：
1. 歐拉費馬定理：a^(phi(m))%m=1（麻麻煩煩）
2. 費馬小定理：a^(p-1)%m=1（用歐拉費馬證）

介紹完可愛的phi，就來講解這題
這題其實就是要用我剛剛提到的東西歐～（（不然我提屁阿＋＋
題目好像很複雜，但稍稍想一下，就可以轉變成求1~n中有幾組數字互質
（因為，當某組（x,y）互質時，他們就不能約分成另一組整數的（x', y'））
所以其實就是求phi(1)~phi(n)的總和嘛～easy，但重點是要怎麼很快的求＝＝
你很快就會發現，因為他有phi(x)= x*[ (p1-1)*(p2-1)*(p3-1)*... ] / [ p1*p2*p3*... ]的性質
這時你就可以用偏廢的質數篩法，去建出phi(1)~phi(n)的值，約O( n^(3/2) )或小一點吧？！＠＠
其實這樣寫在加上一些簡陋的加速，就可以過了，差不多會是排名的最後一名XD
但是由於最後一名看起來過廢， 所以你決定要加速。你想把普通的篩法改成更快的線性篩法。
而這時，你就會開始想線性篩法怎麼寫...
a. 若是質數，就把它放進質數箱子裡。
b. 跑過所有質數箱裡有的東西，乘上當下數字
    1) 若超過上限就break
    2) 把那個數字打勾 <- 意味著不管如何都要打勾那個數字，如除4*2，無其他方式乘出8
    3) 若當下數字是當下質數的倍數就break（4*2後, 4*3是多餘的，因之後的6*2就會做到）
想完了後，你就發現這根本就是你要的阿！！因為每一個數字都會被做出一次，剛剛好O(n)這樣就可以超迅速跑完了！你開始動手把『線性篩法』變成『線性產phi法』
a. 若是質數，把它放進質數箱子中，順便用特性一求得他的phi值
b. 跑過所有質數箱裡有的東西，乘上當下數字
    1) 若超過上限就break
    2) 若當下數字是當下質數的倍數，用特性三與四，得到數字phi值，並break
    3) 把那個數字打勾，並順便用特性四得到phi值
再加一些瑣碎小東西，於是你便AC了

http://codepad.org/hJvP6x3d