poj 2154 Color 欧拉函数优化的ploya计数

枚举位移肯定超时，对于一个位移i。我们须要的是它的循环个数，也就是gcd(i,n)，gcd(i,n)个数肯定不会非常多，由于等价于n的约数的个数。

所以我们枚举n的约数。对于一个约数k，也就是循环个数为n/k这种个数有phi[k]种，证明网上有非常多。

所以答案就是 phi[k]*(pow(n,n/k)) (k是n的全部约数)

因为约数会非常大所以不能打表，仅仅能单个算。

再因为最后要除以n，假设做除法就不能直接取模，所以我们在算每一次pow(n,n/k)的时候，都少乘一个n，这样就相当于除法了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000000;
int quickpow(int m,int n,int k)
{
int ans=1;
while(n)
{
if(n&1) ans=(ans*m)%k;
n=(n>>1);
m=(m*m)%k;
}
return ans;
}
bool a[N];
int prim[N];
int pp[N];
void Prime()
{
memset(a, 0, sizeof(a));
int num = 0, i, j;
pp[1]=1;
for(i = 2; i < N; ++i)
{ if(!(a[i])) prim[num++]=pp[i]=i;
for(j = 0; (j<num && i*prim[j]<N); ++j)
{
pp[i*prim[j]]=prim[j];
a[i*prim[j]] = 1;
if(!(i%prim[j])) break;
}
}
}
int phi(int x)
{
int i,j;
int num = x;
for(i = 0; prim[i]*prim[i] <= x; i++)
{
if(x % prim[i] == 0)
{
num = (num/prim[i])*(prim[i]-1);
while(x % prim[i] == 0)
{
x = x / prim[i];
}
}
}
if(x != 1) num = (num/x)*(x-1);
return num;
}
int main()
{
Prime();
int cas,n,p;
scanf("%d",&cas);
while(cas--)
{
int ans=0;
scanf("%d%d",&n,&p);
for(int l=1;l*l<=n;l++)
{
if(n%l==0)
{
if(l*l==n)
{
ans+=phi(l)%p*quickpow(n%p,l-1,p);
ans%=p;
break;
}
ans+=phi(l)%p*quickpow(n%p,n/l-1,p);
ans+=phi(n/l)%p*quickpow(n%p,l-1,p);
ans%=p;
}
}
printf("%d\n",ans);
}
return 0;
}