poj2154Color polya定理+歐拉函數優化

沒想到賤賤的資料居然是錯的。。搞得我調了一中午+晚上一小時（哦不d飛LJH掉RP畢竟他是BUFF）結果重判就對了五次。。

回歸正題，這題傻子都看得出是polya定理（如果你不是傻子就看這裡），還沒有翻轉，就一個旋轉，結果我就歡快的打完交上去了。傻子都知道會TLE，n<=1e9啊，O(n)都原地爆炸，那怎麼辦。。。一臉懵逼（然後就膜題解了）

可以發現，這題公式就是sigma(gcd(k,n))(k=1~n)，然後該怎麼優化呢，我(??)發現gcd(k,n)裡面肯定有一些k和n的gcd是相同的，那我們設n=i*gcd，k=j*gcd，那i肯定和j互質并且1<=j<=i，而且可以發現，gcd(i*gcd,j*gcd)=gcd,隻要知道j有多少個，就讓power(n,n/i)乘上這個個數，那gcd=n/i的所有情況就都解決了，那具體j有多少個呢？顯而易見(??)就是歐拉函數值(然而我不會)了，那我們O(sqrt(n))枚舉i，然後就可以得出gcd，然後就可以求出歐拉函數值，那就是phi(i)*power(n,n/i)

pain and happy in the cruel world.