你随便写一下出来，发现polya原理的式子里面好多gcd是相同的，gcd（n，i）=k可以改写成gcd（n/k,i/k）=1，也就是说指数为k的项的个数为phi（n/k），就很好求了，最后除的那个n直接放到指数上即可，没必要用逆元。

import java.util.*;import java.io.*;public class Main {	public static int phi(int n){		int ans=n;		for(int i=2;i*i<=n;++i){			if(n%i==0){				ans=ans/i*(i-1);				while(n%i==0){					n/=i;				}			}		}		if(n>1){			ans=ans/n*(n-1);		}		return ans;	}	public static int Quick_Pow(int x,int p,int MOD){		if(p==0){			return 1;		}		int ans=Quick_Pow(x,p>>1,MOD);		ans=(ans*ans)%MOD;		if((p&1)==1){			ans=(x%MOD*ans)%MOD;		}		return ans;	}	public static void main(String[] argc){		int T,n,P;		Scanner sc = new Scanner (new BufferedInputStream(System.in));		T=sc.nextInt();		for(int zu=1;zu<=T;++zu){			int ans=0;			n=sc.nextInt();			P=sc.nextInt();			for(int i=1;i*i<=n;++i){				if(n%i==0){					ans=(ans+((phi(n/i)%P)*Quick_Pow(n,i-1,P))%P)%P;//					System.out.printf("Test:%d\n",ans);					if(i*i!=n){						ans=(ans+((phi(i)%P)*Quick_Pow(n,n/i-1,P))%P)%P;//						System.out.printf("Test:%d\n",ans);					}				}			}			System.out.println(ans);		}		sc.close();    }}