POJ 2154-Color（Polya定理-旋转串项链）

爱被打了一巴掌 2022-06-17 05:52 199阅读 0赞

Color

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;10352</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3368</td> 
  </tr> 
 </tbody> 
</table>

Description

Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected.  
  
You only need to output the answer module a given number P.

Input

The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.

Output

For each test case, output one line containing the answer.

Sample Input

5
    1 30000
    2 30000
    3 30000
    4 30000
    5 30000

Sample Output

1
    3
    11
    70
    629

Source

[POJ Monthly][],Lou Tiancheng

## 题目意思： ##

给定m种颜色的珠子，每种颜色的珠子个数不限，将它们串成长度为n的项链，计算一共能做成多少种不重复的项链。仅考虑旋转，不考虑翻转。

## 解题思路： ##

旋转，将项链顺时针旋转i格之后，其循环节数是gcd(n,i)，计算出所有不同的着色方案。

枚举i会TLE，所以用欧拉函数优化，每个循环的长度L=N/gcd(i,N)，结果是∑(Euler(L)×N^(L-1))%P。

#include<cstdio>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int quick(int a,int b,int m )//a^b%m 快速幂取模
    {
        int ans=1;
        a%=m;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%m;
                --b;
            }
            b/=2;
            a=a*a%m;
        }
        return ans;
    }
    int Euler(int n)//欧拉函数
    {
        int i,ans=n;
        for(i=2; i*i<=n; ++i)
            if(n%i==0)
            {
                ans-=ans/i;
                while(n%i==0)
                    n/=i;
            }
        if(n>1)
            ans-=ans/n;
        return ans;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n,p,ans=0;
            scanf("%d%d",&n,&p);
            int i;
            for(i=1; i*i<n; i++)
                if(n%i==0) //如果i是n的约数，则n/i也是n的约数，也要做同样的处理
                {
                    ans=(ans+(Euler(n/i)%p)*quick(n,i-1,p))%p ;
                    ans=(ans+(Euler(i)%p)*quick(n,n/i-1,p))%p ;
                }
            if(i*i==n) ans=(ans+(Euler(i)%p)*quick(n,i-1,p))%p ;
            printf("%d\n",ans);
        }
        return 0;
    }

[POJ Monthly]: http://poj.org/searchproblem?field=source&key=POJ+Monthly