「POJ2154」Color
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
|
1 2 3 4 5 6 |
5 1 30000 2 30000 3 30000 4 30000 5 30000 |
Sample Output
|
1 2 3 4 5 |
1 3 11 70 629 |
题解
\(ans=\sum_{L|n}n^{L-1} \phi(n/L)\)，求这个式子的值。。。枚举L，根号n求欧拉函数，由于n的约数个数远小于\(\sqrt n\)，求欧拉函数可以枚举质数。。。所以实际上还是很快的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 20101009 #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int tot,T; int n,K,ans; int pri[1000005]; bool mark[1000005]; int qpow(int a,int b) { int ans=1;a%=K; for(int i=b;i;i>>=1,a=a*a%K) if(i&1)ans=ans*a%K; return ans; } int phi(int n) { int ans=n; for(int i=1;pri[i]<=sqrt(n);i++) if(n%pri[i]==0) { ans=(ans-ans/pri[i]); while(n%pri[i]==0)n/=pri[i]; } if(n!=1)ans=(ans-ans/n); return ans%K; } void pre() { for(int i=2;i<=1000000;i++) { if(!mark[i])pri[++tot]=i; for(int j=1;j<=tot&&pri[j]*i<=1000000;j++) { mark[pri[j]*i]=1; if(i%pri[j]==0)break; } } } int main() { pre(); T=read(); while(T--) { n=read();K=read(); ans=0; for(int i=1;i*i<=n;i++) if(n%i==0) { ans+=phi(i)*qpow(n,n/i-1); if(i*i!=n)ans+=phi(n/i)*qpow(n,i-1); ans%=K; } printf("%d\n",ans); } return 0; } |
Subscribe
计数器 9528971
OI 课件=>
OI 课件=>