POJ2154 Color(Polya定理)
Time Limit: 2000MS | Memory Limit: 65536K | |
|---|---|---|
Total Submissions: 11654 | Accepted: 3756 |
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 30000Sample Output
1
3
11
70
629Source
POJ Monthly,Lou Tiancheng
Polya定理：
假设$G$是$p$个对象的一个置换群，用$m$种颜色涂染$p$个对象，则不同颜色的方案数为
$L = \frac{1}{|G|}\sum_{g_i \in G}m^{c(g_i)}$
$G = \{g_1, g_2, \dots g_s \}$，$c(g_i)$为置换$g_i$的循环节数
本题而言第$i$种置换的循环节数为$gcd(n, i)$
因此答案为$L = \frac{1}{n}\sum_{i = 1}^n n^{gcd(i, n}$
枚举约数，用欧拉函数计算，时间复杂度$O(T\sqrt(N) f(n))$，$f(n)$表示小于$\sqrt(n)$的质因子的个数
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#define LL long long
const int MAXN = 1e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int T, N, mod;
int fastpow(int a, int p, int mod) {
int base = 1; a %= mod;
while(p) {
if(p & 1) base = (base * a) % mod;
a = (a * a) % mod; p >>= 1;
}
return base % mod;
}
int prime[MAXN], tot, vis[MAXN];
void Prime() {
for(int i = 2; i <= MAXN - 10; i++) {
if(!vis[i]) prime[++tot] = i;
for(int j = 1; j <= tot && prime[j] * i <= MAXN - 10; j++) {
vis[i * prime[j]] = 1;
if(!i % prime[j]) break;
}
}
}
int phi(int x, int mod) {
int limit , ans = x;
for(int i = 1; i <= tot && prime[i] * prime[i] <= x; i++) {
if(!(x % prime[i])) {
ans = ans - ans / prime[i];
while((x % prime[i]) == 0) x /= prime[i];
}
}
if(x > 1) ans = ans - ans / x;
// printf("%d", ans % mod);
return ans % mod;
}
main() {
T = read();
Prime();
while(T--) {
N = read(); mod = read();
int ans = 0, now = N;
for(int d = 1; d * d<= N; d++) {
if(d * d == N)
ans = (ans + fastpow(N, d - 1, mod) % mod * phi(N / d, mod) % mod) % mod;
else if( (N % d) == 0) {
ans = (ans + fastpow(N, d - 1, mod) * phi(N / d, mod) + fastpow(N, N / d - 1, mod) * phi(d, mod)) % mod;
}
//printf("%d\n", ans);
}
//if(now > 0) ans += fastpow(N, now - 1, mod) * phi(N / now, mod);
printf("%d\n", ans % mod);
}
}