poj 2154 Color < 组合数学+数论>

题意：给出两个整数 N 和 P，表示 N 个珠子，N种颜色，要求不同的项链数，结果 %p ~

思路：利用polya定理解~定理内容：

设 $frac{ }{G}$ 是n个对象的一个置换群, 用m种颜色染图这n个对象，则不同的染色方案数为：

$L =frac{1}{left | {overline{G}} ight |}left [ {m^{c(overline{P_1})}+m^{c(overline{P_2})}+ ...+m^{c(overline{P_g})}} ight ]$ 其中

$overline{G}= { overline{P_1}, overline{P2}, ...,overline{P_g}}$ ，

$c(overline{P_k})$ 为

$overline{P_k}$ 的循环节数~

本题只有旋转一种置换方式，那么共有 N 个置换，每个置换的循环节为 gcd(N,i)~

那么结果为∑(N^(gcd(N, i))) %P。 N为 1e9, 不能枚举 i , 但我们可以统计 gcd(N,i)==a 的有多少个~

令L==N/a, i==a*t, 即 a==gcd(N, i)==gcd(L*a, t*a), 此时只要满足 gcd(L, t)==1即可. 而1<=i<=N 即 1<=t<=N/a==L~

所以t的个数为 L 的欧拉函数, 所以结果为:∑(Euler(L)*(n^(N/L)))%p ,为了避免最后做除法结果可化为∑(Euler(L)*(n^(N/L-1)))%p。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int MN = 5e4;
 5 typedef long long LL;
 6 int a[MN],p[MN], T, N, M, k;
 7 LL P_M( int a, int b )
 8 {
 9     LL res=1, t=(LL)a%M;
10     while(b){
11         if(b&1)res=(res*t)%M;
12         t=(t*t)%M;
13         b>>=1;
14     }
15     return res;
16 }
17 void getp( )
18 {
19     for( int i=3; i*i<=MN; i+=2 ){
20         if(!a[i])
21         for( int j=i+i; j<=MN; j+=i )
22             a[j]=1;
23     }
24     p[0]=2, k=1;
25     for( int i=3; i<MN ; i+=2 )
26         if(!a[i]) p[k++]=i;
27 }
28 int Euler( int x)
29 {
30     int res=x;
31     for( int i=0; i<k&&p[i]*p[i]<=x; ++ i ){
32         if(x%p[i]==0){
33             res=res/p[i]*(p[i]-1);
34             while(x%p[i]==0){
35 
36                  x=x/p[i];
37             }
38         }
39     }
40     if(x>1)
41         res=res/x*(x-1);
42     return res;
43 }
44 int main( )
45 {
46     getp();
47     scanf("%d", &T);
48     while(T--){
49         scanf("%d%d", &N, &M);
50         int i;
51         LL ans=0;
52         for( i=1; i*i<N; ++ i ){
53 
54             if(N%i==0){
55                   ans+=(LL)Euler(i)%M*P_M(N, N/i-1);
56                   ans%=M;
57                   ans+=(LL)Euler(N/i)%M*P_M(N, i-1);
58                   ans%=M;
59             }
60 
61         }
62         if(i*i==N){
63             ans+=(LL)Euler(i)%M*P_M(N, i-1);
64             ans%=M;
65         }
66         printf("%lld
", ans);
67     }
68     return 0;
69 }

View Code