2154 Color//POLYA

Color
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 2967
 
Accepted: 1016
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
/* 제목은 N색 N개의 부등가 교환 개수(modp) N<= 10^9 교환은 회전하는 방식만 있다. 그러면 n개의 교환 기본 지식이 있다. 링의 개수는 gcd(n, i), 길이는 L=n/gcd(n, i) 중 i가 회전하는 자리수는 일반 구법: ∑n^(gcd(n, i) 0<=i #include con st int N=40000;int prime_num; int prime[20000]; int n,p; bool isprime[N]; void init() { memset(isprime,true,sizeof(isprime)); for(int i=2;i*i

좋은 웹페이지 즐겨찾기