poj2154

题目意思：给定N种颜色的珠子，每种颜色个数不限，现做成长度为N的相连，问有多少种方案(只考虑旋转)。答案要mod P

思路:因为只有旋转，所以基本思路就跟poj1286差不多，而且还要简单些，

难的话就是因为N太大了，直接算肯定TLE的。。怎么办？

我们设 a= gcd（N， i) , L= N /a, T = i / a; 那么 gcd（L, T）= 1

所以对于某一个T，只要T与L互质，那么 T*a与 N最大公约数必然为a

那么就转化成找与T互质的数的个数了，这就得用到欧拉函数了。。

最后结果为 sigma（Euler(L) * N ^ (l-1) ）% p

code:

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <cstdio>
 7 
 8 using namespace std;
 9 typedef __int64 LL;
10 int T , a[50001], bo[50001], tot;
11 LL n, p, sum;
12 
13 void init(){
14     tot = 0;
15     for (int i =2; i <= 50000; ++i)
16         if (!bo[i]) {
17         for (int j = i+i; j <= 50000; j += i)
18               bo[j] = 1;
19         a[++tot] = i;
20     }
21 
22 }
23 
24 int phi(int now){ //求欧拉函数 
25     int rea = now;
26     for (int i = 1; a[i]*a[i] <= now; ++i)
27         if (now % a[i] == 0){
28              rea -= rea / a[i];
29              while (now % a[i] == 0) now /= a[i];
30         }
31     if (now > 1) rea -= rea / now;
32     return rea;
33 }
34 
35 LL quick(int x, int k){ //快速幂优化 
36     if (k == 1) return x;
37     if (k == 0) return 1;
38     LL tmp = quick(x, k / 2);
39     tmp = (tmp * tmp) % p;
40     if (k&1) tmp = (tmp * x) % p;
41     return tmp;
42 }
43 
44 void work(int now){
45      LL l = phi(now);
46      sum = (sum + l * quick(n % p, n / now - 1)) % p;
47 }
48 
49 void solve(){
50      sum = 0;
51      scanf("%I64d%I64d", &n, &p);
52      for (int i = 1; i * i <= n; ++i)
53         if (n % i == 0){
54              work(i);
55         //     printf("i = %d\n", i);
56           //   printf("i = %d\n", n / i);
57              if (i*i != n) work(n / i);
58         }
59 
60      printf("%I64d\n", sum);
61 }
62 
63 int main(){
64      freopen("poj2154.in", "r", stdin);
65      freopen("poj2154.out","w", stdout);
66      scanf("%d", &T);
67      init();
68      for (int i =1; i <= T; ++i)
69           solve();
70      fclose(stdin); fclose(stdout);
71 }