【POJ 2154】Color（置換群）

Color

Time Limit: 2000MS Memory Limit: 65536K

Total Submissions: 9265 Accepted: 3010

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

[題意][将正n邊形的n個頂點用n種顔色染色，問有多少種方案（答案mod p，且可由旋轉互相得到的算一種）]

【題解】【與前面幾題相似，但此題沒有旋轉，但資料範圍相當惡心，是以，要優化】

∑ni=1 ngcd(i,n)

= ∑ni=1 ∑nd=1 n[(i,n)=d]

= ∑[d|n]∗φ( d n )∗nd

按照這個公式篩歐拉函數，但因為範圍過大，是以，不可能全部篩出，篩一半，另一半，用下面的方法

根号n的時間内求一個數的phi
inline int find(int m)
{
    int i,k=m,l=m;
    for (i=;i*i<=m;++i)
     if (!(l%i))
      {
        k=k-k/i;
        do{  l/=i;  }while(!(l%i));
      }
    if (l>) k=k-k/l;
    return k;
}
           

由于範圍過大，枚舉的時候隻能枚舉一半，而且要謹慎使用long long

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int prime[],phi[];
int m,n,mod;
bool p[];

inline void shai(int m)
{
    int i,j;
    phi[]=; p[]=;
    for(i=;i<=m;++i)
      {
        if(!p[i])  prime[++prime[]]=i,phi[i]=i-;
        for(j=;j<=prime[];++j)
         {
            if(i*prime[j]>m) break;
            p[i*prime[j]]=;
            if(!(i%prime[j])) 
              {phi[i*prime[j]]=phi[i]*prime[j]; break;}
             else phi[i*prime[j]]=phi[i]*(prime[j]-);
          } 
      }
    return;
}
ll poww(int x,int q)
{
    if(!q) return ;
    if(q==) return x%mod;
    if(q==) return x*x%mod;
    if(q%2)
      {ll sum=poww(x,q/)%mod;  sum=sum*sum*x%mod;  return sum%mod;}
     else
      {ll sum=poww(x,q/)%mod; sum*=sum; return sum%mod; }
}
inline ll get_phi(int x)
{
    if(x<=) return phi[x];
    ll ans=x;
    int i;
    for(i=;i*i<=x;++i)
     if(!(x%i))
      {
        ans=ans*(i-)/i;
        while(!(x%i)) x/=i;
      }
    if(x>) ans=ans*(x-)/x;
    return ans%mod;
}

int main()
{
    int i,j;
    shai();
    scanf("%d",&n);
    for(j=;j<=n;++j)
     {
        ll ans=;
        scanf("%d%d",&m,&mod);
        for(i=;i*i<=m;++i) 
          if(!(m%i))
           {
            ll s1=get_phi(i); ll s2=get_phi(m/i);
            if(m/i==i) ans=(ans+s2*poww(m%mod,i-))%mod;
             else ans=(ans+s2*poww(m%mod,i-))%mod,
            ans=(ans+s1*poww(m%mod,m/i-1))%mod; 
           }
        printf("%I64d\n",ans%mod);
     }
    return 0;
}