首页 > 代码库 > poj 2154 Color 欧拉函数优化的ploya计数
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。