Color
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 3175 |
|
Accepted: 1084 |
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
Polya，只有旋轉，沒有反射，歐拉函數優化。
1 #include <stdio.h>
2 #include <string.h>
3
4 #define L 50000
5
6 int nPrime, prime[ L ];
7
8 void initPrime() {
9 int i, j;
10 nPrime = 0;
11 memset( prime, 0, sizeof(prime) );
12 for ( i = 2; i < L; ++i ) {
13 if( prime[ i ] == 0 ) {
14 prime[ nPrime++ ] = i;
15 for ( j = i+i; j < L; j+=i ) {
16 prime[ j ] = 1;
17 }
18 }
19 }
20 }
21
22 int phi( int n ) {
23 int i, ans = n;
24 for ( i = 0; (i<nPrime)&&(prime[i]*prime[i]<=n); ++i ) {
25 if ( n % prime[ i ] == 0 ) {
26 ans = ans / prime[ i ] * ( prime[ i ] - 1 );
27 do {
28 n /= prime[ i ];
29 } while ( n % prime[ i ] == 0 );
30 }
31 }
32 if ( n != 1 ) {
33 ans = ans / n * (n-1);
34 }
35 return ans;
36 }
37
38 int power( int a, int b, int m ) {
39 int t = 0, ans = 1;
40 a %= m;
41 while ( (1<<t) < b ) {
42 ++t;
43 }
44 while ( t >= 0 ) {
45 ans = ( ans * ans ) % m;
46 if ( (1<<t) & b ) {
47 ans = ( ans * a ) % m;
48 }
49 --t;
50 }
51 return ans;
52 }
53
54 int solve( int n, int p ) {
55 int i, ans = 0;
56 for ( i = 1; i*i < n; ++i ) {
57 if ( n % i == 0 ) {
58 ans = ( ans + phi( i ) % p * power( n, n/i-1, p ) ) % p;
59 ans = ( ans + phi( n/i ) % p * power( n, i-1, p ) ) % p;
60 }
61 }
62 if ( i*i == n ) {
63 ans = ( ans + phi( i ) % p * power( n, i-1, p ) ) % p;
64 }
65 return ans;
66 }
67
68 int main() {
69 int td, n, p;
70 initPrime();
71 scanf( "%d", &td );
72 while ( td-- > 0 ) {
73 scanf( "%d%d", &n, &p );
74 printf( "%d\n", solve( n, p ) );
75 }
76 return 0;
77 }
78