> //第一类环排列 
> #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，但还是wa (0) y07yangruilong 2007-10-30 20:24:28