没想到贱贱的数据居然是错的。。搞得我调了一中午+晚上一小时（哦不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)
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
bool v[];
int pr,prime[];
void linear_prime()
{
memset(v,true,sizeof(v));
for(int i=;i<=;i++)
{
if(v[i]==true)prime[++pr]=i;
for(int j=;j<=pr&&i*prime[j]<=;j++)
{
v[i*prime[j]]=false;
if(i%prime[j]==)break;
}
}
}
int n,mod;
int power(int A,int k)
{
int ans=;A%=mod;
while(k!=)
{
if(k%==)ans=(ans*A)%mod;
A=(A*A)%mod;k/=;
}
return ans;
}
int phi(int x)//求欧拉函数值，即j的种数
{
int ans=x;
for(int i=;prime[i]*prime[i]<=x;i++)
{
if(x%prime[i]==)
{
ans=ans-ans/prime[i];
while(x%prime[i]==)x/=prime[i];
}
}
if(x!=)ans=ans-ans/x;
return ans%mod;
}
int main()
{
linear_prime();
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&mod);
int ans=;
//设n=i*gcd 而 k=j*gcd，用欧拉函数将所有j的值求出
for(int i=;i*i<=n;i++)
{
if(n%i==)
{
ans=(ans+phi(i)*power(n,n/i-))%mod;//循环节为gcd
if(i*i!=n)ans=(ans+phi(n/i)*power(n,i-))%mod;
//这里两个power为什么要-1？由于要%mod，所以求值的时提早将/G（G=n）给做了
}
}
printf("%d\n",ans);
}
return ;
}