給你 n,求出 <n 且 與n互質 的數有幾個。

雖然可以直接 gcd+O(n) 硬爆,但還是寫點有意義的好了。

還記得 phi 函數嗎?

phi(x) 就是 求 <x 且與x互質 的個數,剛好就是這題啊。

假設 x 的質因數有 p1, p2, p3, .... pk :

phi(x) = x * (p1-1)/(p1) * (p2-1)/(p2) * (p3-1)/(p3) * .... * (pk-1)/pk。

我的code

http://snipt.org/zffje2

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()