题意：给你N种颜色的珠子，个数不限，串成一个长度为N的项链，经过旋转以后，问能形成多少等价类

  分析：套用Polya定理的计数公式即可，题目中的旋转操作可以形成N个置换，假设旋转了i个珠子，那么这个置换的置换环个数为gcd(i,N)，但是这里N比较大，需要枚举N的所有因子然后欧拉函数优化。这个题当时我还在想模的数不是质数，逆元怎么办，然后才发现置换群的大小是N，颜色的个数也是N，不需要逆元（笑哭），还有就是这题数据挺强的，时间上尽量多优化一些。

  代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define LL long longconst int N = 1e6+6;bool isp[N];int cnt,P[78598];LL ol[N];void init(){    cnt=0; int up = 1000000;    for(int i=2;i<=up;i++){        if(!isp[i]){            P[cnt++]=i;            ol[i] = i-1;        }        for(int j=0;j
         
           up) break;            isp[tmp] = 1;            if(i%P[j] == 0){                ol[tmp] = ol[i]*P[j];                break;            }else {                ol[tmp] = ol[i]*(P[j]-1);            }        }    }    ol[1] = 1;//    cout<
          
           <
           
             n) break; if(n%P[i] == 0){ res = res/P[i]*(P[i]-1); } while(n%P[i] == 0) n/=P[i]; } if(n!=1) res = res/n*(n-1); return res%p;}LL Pow(LL x,int y){ LL res = 1; while(y){ if(y&1){ res=(res*x)%p; } x=(x*x)%p; y>>=1; } return res;}int read(){ int res=0; char ch; while((ch=getchar())){ if(ch>='0'&&ch<='9'){ res = ch-'0'; break; } } while((ch=getchar())){ if(ch<'0'||ch>'9') break; res *= 10; res += ch-'0'; } return res;}int main(){ init(); int T,n; T = read(); while(T--){ n = read(); p = read(); LL ans = 0; for(int i=1;i*i<=n;i++){ if(n%i == 0){ ans=(ans+(Euler(n/i)*Pow(n,i-1))%p)%p; int p2 = n/i; if(p2!=i) { ans=(ans+(Euler(n/p2)*Pow(n,p2-1))%p)%p; } } } printf("%lld\n",ans); } return 0;}