poj 2154 Color < 组合数学+数论>

链接：http://poj.org/problem?id=2154

题意：给出两个整数 N 和 P，表示 N 个珠子，N种颜色，要求不同的项链数，结果 %p ~

思路：利用polya定理解~定理内容：

设是n个对象的一个置换群, 用m种颜色染图这n个对象，则不同的染色方案数为：

其中

，

为

的循环节数~

本题只有旋转一种置换方式，那么共有 N 个置换，每个置换的循环节为 gcd(N,i)~

那么结果为∑(N^(gcd(N, i))) %P。 N为 1e9, 不能枚举 i , 但我们可以统计 gcd(N,i)==a 的有多少个~

令L==N/a, i==a*t, 即 a==gcd(N, i)==gcd(L*a, t*a), 此时只要满足 gcd(L, t)==1即可. 而1<=i<=N 即 1<=t<=N/a==L~

所以t的个数为 L 的欧拉函数, 所以结果为:∑(Euler(L)*(n^(N/L)))%p ,为了避免最后做除法结果可化为∑(Euler(L)*(n^(N/L-1)))%p。

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int MN = 5e4;

 typedef long long LL;

 int a[MN],p[MN], T, N, M, k;

 LL P_M( int a, int b )

 {

     LL res=, t=(LL)a%M;

     while(b){

         if(b&)res=(res*t)%M;

         t=(t*t)%M;

         b>>=;

     }

     return res;

 }

 void getp( )

 {

     for( int i=; i*i<=MN; i+= ){

         if(!a[i])

         for( int j=i+i; j<=MN; j+=i )

             a[j]=;

     }

     p[]=, k=;

     for( int i=; i<MN ; i+= )

         if(!a[i]) p[k++]=i;

 }

 int Euler( int x)

 {

     int res=x;

     for( int i=; i<k&&p[i]*p[i]<=x; ++ i ){

         if(x%p[i]==){

             res=res/p[i]*(p[i]-);

             while(x%p[i]==){

                  x=x/p[i];

             }

         }

     }

     if(x>)

         res=res/x*(x-);

     return res;

 }

 int main( )

 {

     getp();

     scanf("%d", &T);

     while(T--){

         scanf("%d%d", &N, &M);

         int i;

         LL ans=;

         for( i=; i*i<N; ++ i ){

             if(N%i==){

                   ans+=(LL)Euler(i)%M*P_M(N, N/i-);

                   ans%=M;

                   ans+=(LL)Euler(N/i)%M*P_M(N, i-);

                   ans%=M;

             }

         }

         if(i*i==N){

             ans+=(LL)Euler(i)%M*P_M(N, i-);

             ans%=M;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

巴特西

poj 2154 Color < 组合数学+数论>

最新文章

热门文章