普通的polya问题，用枚举质因数、欧拉函数优化。
这题开long long可能会T。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 100050 using namespace std; int t,n,mod,prime[maxn],tot=0; bool vis[maxn]; void get_table() { for (int i=2;i<=maxn-50;i++) { if (!vis[i]) prime[++tot]=i; for (int j=1;j<=tot && i*prime[j]<=maxn-50;j++) { vis[i*prime[j]]=true; if (!i%prime[j]) break; } } } int f_pow(int a,int b) { a%=mod; int base=a,ans=1; while (b) { if (b&1) ans=(ans*base)%mod; base=(base*base)%mod; b>>=1; } return ans; } int phi(int x) { int ret1=1,ret2=1,top=x; for (int i=1;i<=tot && prime[i]*prime[i]<=top;i++) { if (x%prime[i]) continue; ret1*=(prime[i]-1);ret2*=prime[i]; while (x%prime[i]==0) x/=prime[i]; } if (x!=1) {ret1*=(x-1);ret2*=x;} double rr=(double)top/ret2*ret1; return (int)rr%mod; } void work() { int top=sqrt(n),ans=0; for (int i=1;i<=top;i++) { if (n%i) continue; ans+=f_pow(n,i-1)*phi(n/i)%mod;ans%=mod; if ((i!=top) || (top*top!=n)) { ans+=f_pow(n,n/i-1)*phi(i)%mod; ans%=mod; } } printf("%d ",ans); } int main() { scanf("%d",&t); get_table(); for (int i=1;i<=t;i++) { scanf("%d%d",&n,&mod); work(); } return 0; }