首页 > 代码库 > poj2409 & 2154 polya计数+欧拉函数优化
poj2409 & 2154 polya计数+欧拉函数优化
这两个题都是项链珠子的染色问题
也是polya定理的最基本和最经典的应用之一
题目大意： 用m种颜色染n个珠子构成的项链，问最终形成的等价类有多少种
项链是一个环。通过旋转或者镜像对称都可以得到置换
旋转可以旋转 i=[1，n]次。。画图可以看出循环节有gcd(n,i)个
镜像对称的置换画个图也是很容易找的
然后通过polya定理就可以容易的求出等价类的种数了
2409就是这样一个裸题，以下为ac代码
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000long long gcd(long long a,long long b){ return b?gcd(b,a%b):a;}long long pow(long long a,long long b){ long long res=1; while(b) { if(b&1) { res*=a; } a*=a; b>>=1; } return res;}int main(){ long long n,m; while(scanf("%I64d%I64d",&m,&n),n+m) { long long ans=0; for(int i=1;i<=n;i++) { ans+=pow(m,gcd(n,i)); } if(n&1) { ans+=n*pow(m,n/2+1); } else { ans+=n/2*pow(m,n/2)+n/2*pow(m,n/2+1); } printf("%I64d\n",ans/2/n); } return 0;}
2154不允许镜像对称，只考虑旋转的情况
但是n很大。o(n)会超时，因此需要用优化。。
然后去学习了一种欧拉函数优化方法：
只枚举循环节的个数 ，然后计算出这样的置换有多少个，再统计即可
假设某种置换的循环节个数为 d，那么我们所求的就是满足gcd(n,i)=d 的 i 的个数
显然 i 应该是 d的倍数，令i =q*d,再令 n=p*d;
等式变为gcd(p*d,q*d)==d， 即 p，q 互质
而由n>=i 可知 p>=d 要对每一个p，求小于等于p且与p互质的数。。显然是求 p的欧拉函数了
具体见代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define maxn 100000int phi(int n){ int res=n; for(int i=2;i*i<=n;i++) { if(n%i==0) { res=res/i*(i-1); } while(n%i==0) n/=i; } if(n>1) res=res/n*(n-1); return res;}int pow(int a,int b,int mod){ int res=1; a%=mod; while(b) { if(b&1) { res*=a; res%=mod; } a*=a; a%=mod; b>>=1; } return res;}int main(){ int t; int n,p; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&p); int ans=0; for(int i=1;i*i<=n;i++) { if(n%i) continue; if(i*i==n) { ans+=phi(i)%p*pow(n,n/i-1,p); ans%=p; } else { ans+=phi(i)%p*pow(n,n/i-1,p); ans%=p; ans+=phi(n/i)%p*pow(n,i-1,p); ans%=p; } } cout<<ans<<endl; } return 0;}
poj2409 & 2154 polya计数+欧拉函数优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。