//第一类环排列 
#include<stdio.h>
#include<math.h>
int a[10000],b[10000];
int prime[100000],p0[10000],t[10000];
int n,p;
int modn(int base,int pow)//计算base^pow(mod p) 
{
 int i,j,mod,sum;
 __int64 m0;
 mod=p;
 m0=pow;i=0;
 while(m0)
 {a[i]=m0%2;i++;m0/=2;
 }
 m0=base;sum=1;
 for(j=0;j<i;j++)
 {
  if(a[j])sum=(sum*m0)%mod;
  m0=(m0*m0)%mod;
 }
 return sum;
}
int isprime(int n0)
{
 int i;int m;
 if(n0==1)return 0;
 m=(int)sqrt((double)n0);
 for(i=2;i<=m;i++)
 if(n0%i==0)break;
 if(i>m)return 1;
 else return 0;
 }
int main()
{
 int i,j,k,save,fact,sum0,mat,k0,s;
 int test;
 int sum;
 prime[1]=2;prime[2]=3;k=2; 
 for(i=5;i<=100000;i+=2)
 {
 for(j=1;prime[j]*prime[j]<=i;j++)
 {
  if(i%prime[j]==0)goto loop;
}
k++;prime[k]=i;
loop:;
}
prime[0]=k;
 scanf("%d",&test);
 while(test--)
 {
  scanf("%d%d",&n,&p);
  if(n==1){printf("%d\n",1%p);continue;}
  if(n==2){printf("%d\n",3%p);continue;}
  k=0;
  for(i=1;i*i<=n;i++)//计算n所有的因子 
  {if(n%i==0)
  {
   k++;b[k]=i;
   if(b[k]!=n/i){k++;b[k]=n/i;} 
  }
 }
 /*for(i=1;i<=k;i++)
 printf("%d ",b[i]);
 printf("\n");
 */
 //printf("%d\n",modn(4,1));
 fact=0;
 for(i=1;i<=k;i++)
 { mat=b[i];
   //if(b[i]==1)goto loop;
   if(isprime(b[i]))sum0=b[i]-1;
   else
   {
   k0=0;
  for(j=1;j<=prime[0];j++)
   {
 s=0;
 while(b[i]%prime[j]==0){s++;b[i]/=prime[j];}
 if(s>0){k0++;p0[k0]=prime[j];t[k0]=s;}
 if(b[i]==1)break;
 if(b[i]/prime[j]<prime[j]){k0++;p0[k0]=b[i];t[k0]=1;break;}
 }//for
 sum0=mat;
 for(j=1;j<=k0;j++)
 sum0=(sum0/p0[j]*(p0[j]-1))%p;
 }//else
 //printf("%d\n",sum0);
 fact=(fact+sum0*modn(n,n/mat-1))%p;
 //printf("%d\n",fact);
 }//for
 printf("%d\n",fact%p);
 }//while
}//main
/*
63
1000000000 30000
16000
100000000 30000
16000
10000000 30000
16000
1000000 30000
16000
100000 30000
16000
10000 30000
4000
1000 30000
400
100 30000
12040
10 30000
20044
1 30000
1
*/

• 前面几个是10000 (2178) gaosimeng 2007-06-06 02:07:39
  • 我的是10000，但还是wa (0) y07yangruilong 2007-10-30 20:24:28