这两个题都是项链珠子的染色问题
也是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 10000
long 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=;
while(b)
{
if(b&)
{
res*=a;
}
a*=a;
b>>=;
}
return res;
}
int main()
{
long long n,m;
while(scanf("%I64d%I64d",&m,&n),n+m)
{
long long ans=;
for(int i=;i<=n;i++)
{
ans+=pow(m,gcd(n,i));
}
if(n&)
{
ans+=n*pow(m,n/+);
}
else
{
ans+=n/*pow(m,n/)+n/*pow(m,n/+);
}
printf("%I64d\n",ans//n);
}
return ;
}
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 100000
int phi(int n)
{
int res=n;
for(int i=;i*i<=n;i++)
{
if(n%i==)
{
res=res/i*(i-);
}
while(n%i==)
n/=i;
}
if(n>)
res=res/n*(n-);
return res;
}
int pow(int a,int b,int mod)
{
int res=;
a%=mod;
while(b)
{
if(b&)
{
res*=a;
res%=mod;
}
a*=a;
a%=mod;
b>>=;
}
return res;
}
int main()
{
int t;
int n,p;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&p);
int ans=;
for(int i=;i*i<=n;i++)
{
if(n%i)
continue;
if(i*i==n)
{
ans+=phi(i)%p*pow(n,n/i-,p);
ans%=p;
}
else
{
ans+=phi(i)%p*pow(n,n/i-,p);
ans%=p;
ans+=phi(n/i)%p*pow(n,i-,p);
ans%=p;
}
}
cout<<ans<<endl;
}
return ;
}