Color

Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 12707   Accepted: 4049

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

polya计数 讲解

https://blog.csdn.net/liangzhaoyang1/article/details/72639208

https://blog.csdn.net/WhereIsHeroFrom/article/details/79631703

显然  对于每一次置换,有GCD(i,n)个循环

有GCD(i,n)个置换群

 

欧拉sqrt(n)求法会T

利用素数优化

long long 会T全改int 

 

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN = 2e6+12;
int prime[MAXN],check[MAXN];
int ph[MAXN];
int mu[MAXN];
int cnt=0;
int prim[MAXN];
bool vis[MAXN];
void get(int maxn)
{
    ph[1]=mu[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            prim[++cnt]=i;
            mu[i]=-1;ph[i]=i-1;
        }
        for(int j=1;j<=cnt&&prim[j]*i<maxn;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                ph[i*prim[j]]=ph[i]*prim[j];
                break;
            }
            else mu[i*prim[j]]=-mu[i],ph[i*prim[j]]=ph[i]*(prim[j]-1);
        }
    }

}
void getprime()
{
    int i,j;
    for(i = 2;i < MAXN;i++){
        if(check[i] == 0) prime[++prime[0]] = i;
        for(j = 1;j <= prime[0] && prime[j] < MAXN/i;j++){
            check[prime[j]*i] = 1;
            if(i%prime[j] == 0) break;
        }
    }
}
int N,p;
int phi(int d)
{

    //if(d<MAXN)
     //   return ph[d];
    int ans = d,tmp = d;
    for(int i = 1;prime[i]*prime[i] <= tmp;i++){//i <= prime[0] && prime[i] <= tmp 卡常数
        if(tmp%prime[i] == 0)
            ans -= ans/prime[i];
        while(tmp % prime[i] == 0) tmp /= prime[i];
    }
    if(tmp != 1) ans -= ans/tmp;
    return ans;
}
int qpow(int a,int n,int mod)
{
    int ans=1;
    a%=mod;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    int t;
    get(MAXN);
    int mod;
    getprime();
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d%d",&n,&mod);
        long long sum=0;
        for(int i=1; i*i<=n; i++)
        {
            if(n%i==0)
            {
                int la=n/i;
                if(la!=i)
                {
                    sum+=(ll)qpow(n,i-1,mod)*phi(la);
                    sum%=mod;
                }
                sum+=(ll)qpow(n,la-1,mod)*phi(i);
                sum%=mod;
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}