这是道标准的数论优化的polya题。卡时卡的很紧，需要用int才能过。程序中一定要注意控制不爆int！！！我因为爆intWA了好久=_=……
题目简洁明了，就是求 sigma n^gcd(i,n)；但是由于n很大，所以直接暴力枚举必然会T。于是我们按照这种题的通常思路按gcd的值分类。
gcd(i, n) = 1 的个数很明显为 phi(n);
gcd(i, n) = 2 -> gcd(i/2, n/2) = 2 所以个数为 phi(n/2);
这样就ok了， 我们就是要求 sigma phi(n/d) * n^d ， 其中 d 是 n 的因数。
上代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; int n, p; int mi(int a)
{
int ans = , zan = n%p;
while (a)
{
if (a & )
ans = (ans * zan) % p;
a >>= ; zan = (zan * zan) % p;
}
return ans;
} int ouler(int now)
{
int ans = now;
for (int i = ; i*i <= now; ++i)
if (!(now % i))
{
ans = ans / i * (i-);
while (!(now % i)) now /= i;
}
if (now > ) ans = ans / now * (now-);
return ans;
} int main()
{
int T; scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &p);
int ans = ;
for (int i = ; i*i <= n; ++i)
if (!(n % i))
{
ans = (ans + ouler(n/i)%p*mi(i-)) % p; // 两个函数位置一定不能倒过来
if (i * i != n)
ans = (ans + ouler(i)%p*mi(n/i-)) % p; // 不然会超int！！！
}
printf("%d\n", ans % p);
}
return ;
}