首页 > 代码库 > POJ2154 Color

POJ2154 Color

2024-09-14 00:27:46   217人阅读

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 10322 Accepted: 3360

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

51 300002 300003 300004 300005 30000

Sample Output

131170629

Source

POJ Monthly,Lou Tiancheng

 

数学问题 统计 polya原理

仍然是项链的套路，没有翻转只有旋转同构。

需要用到欧拉函数优化

1、数据范围大，要先打好素数筛

2、for统计答案的时候要一起算n和n/i，这样只用循环到sqrt(n)

没加这两个T飞了

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mxn=100101;11 int read(){12     int x=0,f=1;char ch=getchar();13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15     return x*f;16 }17 int pri[mxn],cnt=0;18 bool vis[mxn];19 void init(){20     for(int i=2;i<mxn;i++){21         if(!vis[i])22             pri[++cnt]=i;23         for(int j=1;j<=cnt && (long long)pri[j]*i<mxn;j++){24             vis[pri[j]*i]=1;25             if(i%pri[j]==0)break;26         }27     }28     return;29 }30 int phi(int x){31     int res=x;32     int m=sqrt(x+0.5);33 //    for(int i=1;i<=cnt && x>1;i++){34     for(int i=1;i<=cnt && pri[i]<=m;i++){35         if(x%pri[i]==0){36             res=res/pri[i]*(pri[i]-1);37             while(x%pri[i]==0)38                 x/=pri[i];39         }40     }41 //    printf("x:%d %d\n",x,res);42     if(x>1)res=res/x*(x-1);43     return res;44 }45 int n,p;46 int ksm(int c,int k){47     int res=1;48     while(k){49         if(k&1)(res*=c)%=p;50         c=c*c%p;51         k>>=1;52     }53     return res;54 }55 int main(){56     int i,j;57     int T=read();58     init();59     while(T--){60         n=read();p=read();61         int ans=0;62         for(i=1;i*i<n;i++){63             if(n%i==0){64 //                printf("i:%d phi:%d\n",n/i,phi(n/i));65                 ans+=ksm(n%p,i-1)*(phi(n/i)%p);66                 ans%=p;67                 ans+=ksm(n%p,n/i-1)*(phi(i)%p);68                 ans%=p;69             }70         }71         if(i*i==n)ans=(ans+ksm(n%p,i-1)*(phi(i)%p))%p;72         printf("%d\n",ans%p);73     }74     return 0;75 }

 

POJ2154 Color


联系
我们