| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 11758 | Accepted: 3783 |
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
n种颜色的珠子组成一个长度为n的圆环，旋转能够到达的属于重复状态，问一共有多少种不同的方案。
由polya定理可知 ans=SUM{ ngcd(k,n) | 0<=k<n} / n ，n<1e9 如果直接算的话肯定会T。由于所有的gcd(k,n)都是n的因子，可以考虑对
相同的因子分成一组，这样找到每一组的个数就好办了， ans=1/n * SUM{ s(d)*nd | d|n ,s(d)为使得gcd(k,n)=d成立的k的个数 }，
gcd(k,n)==d --> gcd(k/d,n/d)==1 --> phi(n/d) 。 所以得出s(d)=phi(n/d) ,枚举一下n的因子统计答案就好了。
在计算phi的时候先把sqrt(1e9)之内的素数筛出来再计算会更快，否则会超时。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define PI acos(-1.0)
#define N 33333
int mod;
bool isp[N+];
vector<int>prime;
void init(){
int m=sqrt(N+0.5);
for(int i=;i<=N;i++){
if(!isp[i]){
prime.push_back(i);
for(int j=i*i;j<=N;j+=i)isp[j]=;
}
}
}
int qpow(int a,int b,int m){
a%=m;
int r=;
while(b){
if(b&) r=r*a%m;
b>>=;
a=a*a%m;
}
return r%m;
}
int euler(int n){
int m=sqrt(n+0.5);
int ans=n;
for(int i=;prime[i]<=m;++i){
if(n%prime[i]==){
ans=ans/prime[i]*(prime[i]-);
while(n%prime[i]==) n/=prime[i];
}
}
if(n>) ans=ans/n*(n-);
return ans%mod;
}
int main()
{
int t,n,i,j,k,d;
init();
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&mod);
int ans=;
for(i=;i*i<n;++i){
if(n%i==){
(ans+=(euler(n/i)*qpow(n,i-,mod)%mod))%=mod; (ans+=(euler(i)*qpow(n,n/i-,mod)%mod))%=mod;
}
}
if(i*i==n) (ans+=(euler(i)*qpow(n,i-,mod)%mod))%=mod;
cout<<ans<<endl;
}
return ;
}