POJ 2154 color

发表于 | 分类于 ， |

题目链接

POJ 2154 color

题解

对于一个n元素环染色,先考虑旋转,置换的总数是n个
旋转k个元素后构成的循环数,即轮换数为$gcd(k,n)$
根据polay定理,方案数为
对与于这个式子可以化为

欧拉+快速幂

代码

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,p;
const int maxn = 1000000007;
inline int read() {
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
    return x*f;
}
const int maxm = 1000005;
int pri[maxm],tot=0;bool vis[maxm];
int phi(int x) {
    int ret=x;;
    for(int i=1;pri[i]<=sqrt(x);i++)
        if(x%pri[i]==0) {
            ret=(ret-ret/pri[i]);
            while(x%pri[i]==0)x/=pri[i];
        }
    if(x!=1)ret=(ret-ret/x);
    return ret%p;
}
void getpre() {
    for(int i=2;i<=1000000;i++) {
        if(!vis[i])pri[++tot]=i;
        for(int j=1;j<=tot&&pri[j]*i<=1000000;j++) {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
}
int qpow(int n,int cnt) {
    int ret=1,tmp=n;tmp%=p;
    while(cnt) {
        if(cnt&1) ret=(tmp*ret)%p;
        tmp=tmp*tmp%p;
        cnt>>=1;
    }
    return ret;
}
void dec(int n) {
    int ans=0;
    for(int i=1;i*i<=n;++i) {
        if(i*i==n)ans=(ans+phi(i)*qpow(n,i-1))%p;
        else if(!(n%i)) {
            ans=(ans+qpow(n,i-1)*phi(n/i)+qpow(n,n/i-1)*phi(i))%p;
        }
    }
    printf("%d\n",ans);
}
int main() {
    getpre();
    int cnt=read();
//  for(int i=1;i<=cnt;++i) {
//      printf("%d ",phi[i]);
//  }
    for(;cnt--;) {
        n=read(),p=read();
        dec(n);
    }
    return 0;
}