组合数学 - 波利亚定理 --- poj : 2154 Color

Color

Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 7873   Accepted: 2565

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 30000

Sample Output

1
3
11
70
629

Source

POJ Monthly,Lou Tiancheng
 

Mean:

给你一个包含N个珠子的项链,现在有N种颜色,让你从这N种颜色中选择一些颜色来将这些珠子染色,问可以染出多少种不同的珠子。

analyse:

对于n比较小的情况我们可以直接暴力枚举置换群并统计其对应的C(f),考虑旋转i个珠子的循环群,我们可以证明其对应的不动的染色方案C(fi)=n^gcd(i,n)。为什么呢?我们可以这样考虑,假设珠子编号为0~n-1,对于旋转i个珠子的循环群,由于相邻间的珠子对应的旋转后位置还是相邻,所以这个循环群的环必然是大小相等的。假设其环的大小为T,那么就有(T*i)%n=0。假设T*i=k*n,i=g*x,n=g*y,其中g=gcd(i,n)。那么T=k*y/x,因为k为整数,x、y互质,所以使得T最小且为正整数的k=x,那么T=y,整个循环群中环的个数=n/T=g。所以我们可以得到C(fi)=n^gcd(i,n)。那么这个题目就转化为求sum{n^gcd(i,n)},1<=i<=n。

但是n<=10^9,这个数据范围太大,直接枚举必然超时,我们要考虑优化。观察上面的公式,我们发现虽然i的范围很大,但是gcd(i,n)的值却不多,最多为n的因子的个数。如果我们可以很快求出gcd(i,n)=g时i的个数,那么我们就能够得到一个很高效的算法。假设i=g*x,n=g*y,gcd(i,n)=g的条件为x、y互质,又因为1<=x<=y。所以满足条件的x的个数就是[1,y]里和y互质的数的个数,这就等于phi(y)。欧拉函数的值可以在O(n^(1/2))的复杂度内算出来,于是我们就得到了一个高效的算法。

Time complexity:O(n^(/12))

Source code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; int n, yu; const int NN=10000000;
bool v[NN];
int p[NN];
int len=-1;
void make_p()
{
int i,j;
for(i=2; i<NN; ++i)
{
if(!v[i]) p[++len] = i;
for(j=0; j<=len && i*p[j] < NN; ++j)
{
v[i*p[j]] =1;
if(i%p[j] == 0) break;
}
}
} int work(int n) {
int temp = n;
for (int i = 0; i < len && p[i]*p[i] <= temp; ++i)
{
if (temp % p[i] == 0) {
n -= n/p[i];
do {
temp /= p[i];
}while (temp % p[i] == 0);
}
}
if (temp != 1) {
n -= n/temp;
}
return n%yu;
} int solve(int m) {
int ans = 1;
int s = n%yu;
int temp = m;
while (temp > 0) {
if (temp&1) {
ans = (ans * s) % yu;
}
s = (s*s)%yu;
temp >>= 1;
}
return ans;
} int main() {
make_p();
int t;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &yu);
int res = 0;
for (int i = 1; i*i <= n; ++i) {
if (i*i == n)
{
res = (res + work(i)*solve(i-1))%yu;
}
else if (n%i == 0)
{
res = (res + work(i)*solve(n/i-1) + work(n/i)*solve(i-1))%yu;
}
}
printf("%d\n", res);
}
return 0;
}

  

上一篇:【协议分析】Wireshark 过滤表达式实例


下一篇:MIT Introduction to Computer Science and Programming (Lesson one )