POJ 2154 Color

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

1 30000

2 30000

3 30000

4 30000

5 30000

Sample Output

629

这题不用考虑翻转操作

所以答案就是$ans=sum_{i=1}^nn^{gcd(i,n)}$

枚举gcd，可以得到：

$ans=frac{1}{n}sum_{d=1}^nsum_{i=1}^{n}n^{d}[gcd(i,n)==d]$
$ans=sum_{d=1}^nn^{d-1}sum_{i=1}^{frac{n}{d}}[gcd(i,n/d)==1]$
$ans=sum_{d=1}^nn^{d-1}phi(frac{n}{d})$

外层枚举n因数

求欧拉函数用定义式可以O(√n)求解

这样常数很大

实现筛出素数，求欧拉时只枚举素数

因为n的因数远远小于√n，所以很快，虽然理论上会超

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long lol;
 8 int tot,vis[50001],prime[50001],ans,Mod;
 9 void pre()
10 {int i,j;
11   for (i=2;i<=50000;i++)
12     {
13       if (vis[i]==0)
14     {
15       tot++;
16       prime[tot]=i;
17     }
18       for (j=1;j<=tot;j++)
19     {
20       if (1ll*i*prime[j]>50000) break;
21       vis[i*prime[j]]=1;
22       if (i%prime[j]==0)
23         break;
24     }
25     }
26 }
27 int qpow(int x,int y)
28 {
29   int res=1;
30   while (y)
31     {
32       if (y&1) res=1ll*res*x%Mod;
33       x=1ll*x*x%Mod;
34       y>>=1;
35     }
36   return res;
37 }
38 int phi(int n)
39 {int i;
40   int s=n;
41   for (i=1;i<=tot&&1ll*prime[i]*prime[i]<=n;i++)
42     if (n%prime[i]==0)
43       {
44     s=s-s/prime[i];
45     while (n%prime[i]==0) n/=prime[i];
46       }
47   if (n!=1)
48     s=s-s/n;
49   return s%Mod;
50 }
51 int main()
52 {int T,tim,i,n;
53   cin>>T;
54   pre();
55   while (T--)
56     {
57       scanf("%d%d",&n,&Mod);
58       tim=sqrt(n);
59       ans=0;
60       for (i=1;i<=tim;i++)
61     if (n%i==0)
62       {
63       ans=(ans+1ll*qpow(n,i-1)*phi(n/i)%Mod)%Mod;
64       if (i*i<n)
65         ans=(ans+1ll*qpow(n,n/i-1)*phi(i)%Mod)%Mod;
66     }
67       printf("%d
",ans);
68     }
69 }