首页 > 代码库 > 组合数学 - 波利亚定理 --- poj : 2154 Color
组合数学 - 波利亚定理 --- poj : 2154 Color
Color
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 7873 | Accepted: 2565 |
Description
You only need to output the answer module a given number P.
Input
Output
Sample Input
51 300002 300003 300004 300005 30000
Sample Output
131170629
Source
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;}
组合数学 - 波利亚定理 --- poj : 2154 Color