# coreBugZJ

## Color，POJ 2154

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

`51 300002 300003 300004 300005 30000`

Sample Output

`131170629`

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, 0sizeof(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*< 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*== 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

posted on 2011-04-18 22:24 coreBugZJ 阅读(322) 评论(0)  编辑 收藏 引用 所属分类: ACM