poj 2154：Color

大意：n种颜色的珠子可组成多少种长度为n的项链？

这题和2409 类似，不同之处在于，只考虑旋转，不考虑翻转；

因此相对前面两个题目应该说是更简单，但一看数据范围，

就不是这么回事了，2409完全可以直接循环处理，

但这题目n最大达100000000，显然会TLE，故需寻求更佳的解决方案。

用欧拉函数进行优化：

旋转：顺时针旋转i格的置换中，循环的个数为gcd（i，n），每个循环的长度L为n/gcd(i,n)。

如果枚举旋转的格数i，复杂度显然较高。有没有好方法呢？可以不枚举i，反过来枚举L。

由于L|N,枚举了L，再计算有多少个i使得0<=i<=n-1并且gcd（i,n）＝n/L。

不妨设a＝n/L=gcd(i, n),

不妨设i＝a*t则当且仅当gcd(L,t)=1时

Gcd(i,n)=gcd(a*L,a*t)=a。

因为0<=i<n,所以0<=t<n/a=L.

所以满足这个条件的t的个数为Euler(L).

#include
     
      #include
      
       const int N = 36000;int prime[N];int pnum;bool isp[N];int  mod;void getPrim(){ int i,j; pnum = 0; memset(isp,true,sizeof(isp)); for(i=2;i
       
        >=1;  a=(a*a)%mod; } return ans;}int main(){ getPrim(); int T; scanf("%d",&T); {       while(T--)    {     int  a,l;     int  ans = 0;     scanf("%d%d",&a,&mod);     for(l=1;l*l