题目：http://poj.org/problem?id=2154
置换的第二道题！
需要优化！式子是ans=∑n^gcd(i,n)/n (i∈1~n)，可以枚举gcd=g，则有phi( n/g )个数与n的gcd是g。
g是n的约数，成对出现，可以O(sqrt(n))枚举。用不断 /p 的log(n)做法求单个的phi。(不用专门看p是不是质数，此处可以保证一定是质数)
注意pw里的x传进去要先%mod！！！因为它是1e9级别的，一开始(x*=x)%=mod的时候会爆。
如果把n开成long long，这里传进去long long，就没事了。但会TLE！！！所以还是先取模。
注意各种有除法的地方都不能随时取模。如phi，和ans/n的除法的处理。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int T,mod,n;
ll ans;
int phi(int a)
{
int ret=a;
for(int i=;i*i<=a;i++)
if(a%i==)
{
ret=ret/i*(i-);
// ret-=ret/i;//这样也行！
while(a%i==)a/=i;
}
// if(a!=1)ret-=ret/a;
if(a!=)ret=ret/a*(a-);//剩下一个质因数
return ret%mod;//不要中途%mod，有除法！
}
ll pw(int x,int k)
{
ll ret=;x%=mod;/////x是1e9的，但long long会爆！
while(k){if(k&)(ret*=x)%=mod;(x*=x)%=mod;k>>=;}return ret;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&mod);ans=;
for(int i=;i*i<=n;i++) //i是gcd的话，n/i也是gcd!
{
if(n%i)continue;
(ans+=pw(n,i-)*phi(n/i))%=mod;
if(i*i!=n)(ans+=pw(n,n/i-)*phi(i))%=mod;
}
printf("%lld\n",ans);//不要这里/n，模意义下不行。让上面的pw少乘一个n
}
return ;
}