# POJ 2154 Color （Polya + 欧拉函数）

## 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


## 题意

N 种颜色的珠子要组成长度为 N 的项链，考虑旋转相同的情况算一种，求总共有多少种情况 mod P 。

## AC 代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;

typedef __int64 LL;

const int maxn = 40000;
int N,P;

int pr[maxn];
bool prime[maxn];

void getprime()         //筛法素数表
{
int i,j,k=0;
memset(prime,true,sizeof(prime));
for(i=2; i<maxn; i++)
{
if(prime[i])
{
pr[k++]=i;
for(j=i+i; j<maxn; j+=i)
prime[j]=false;
}
}
}

int phi(int n)      //求欧拉函数
{
int rea=n;
for(int i=0; pr[i]*pr[i]<=n; i++)
{
if(n%pr[i]==0)
{
rea=rea-rea/pr[i];
while(n%pr[i]==0)
n/=pr[i];
}
}
if(n>1)
rea=rea-rea/n;
return rea;
}

int mult(int a,int n)   //快速幂取模
{
if(n<0)return 0;
int ans=1;
while(n)
{
if(n&1)ans=(ans*a)%P;
a=(a*a)%P;
n>>=1;
}
return ans;
}

int main()
{
ios::sync_with_stdio(false);
int T;
getprime();
cin>>T;
while(T--)
{
cin>>N>>P;
int ans=0;
for(int i=1; i*i<=N; i++)
{
if(N%i==0)
{
int no=N/i;
int oula=phi(no)%P;
int foula=0;
if(i*i!=N)
foula=phi(i)%P;
ans=(ans+mult(N%P,i-1)*oula%P+mult(N%P,no-1)*foula%P)%P;
}
}
cout<<ans<<endl;
}
return 0;
}