Color
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 10821
Accepted: 3499
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
Sample Output
Source
POJ Monthly,Lou Tiancheng
[Submit] [Go Back] [Status] [Discuss]
Home Page
Go Back
To top
題意：給你n個珠子組成一個項鍊，讓你用n種顔色給這n個珠子染色，
兩個項鍊一樣目前僅當旋轉已經角度後能重合，問你組成項鍊的方案數。
題解：polya定理計數的模闆題，然而這裡n有10億這麼大，是以不能暴力找gcd(i,n)。
我們設l=n/gcd(n,i)為循環節的長度，則gcd(n,i)=n/l。
我們設cnt=gcd(n,i)，表示循環節的個數。因為cnt一定是i的因數，故設i=cnt*x。
又因為n=cnt*l，故gcd(n,i)=gcd(cnt*l,cnt*x)=cnt，該等式成立當且僅當gcd(l,x)=1
此時問題轉化為求gcd(l,x)=1,時x的個數，也就是求l的歐拉函數（不懂的自行百度歐拉函數）
總複雜度由O(nlog(n)
)變為O(sqrt(n)log(n))。。。。。