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
5
1 30000
2 30000
3 30000
4 30000
5 30000
Sample Output
1
3
11
70
629
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;
}