#include<cstdio>
#include<algorithm>
using namespace std;
const int M=100000;
int prime[10000],p0[10000],t[10000],b[10000];
int gcd(int a,int b)
{
 if(b==0)return a;
 return gcd(b,a%b);
}
int modn(int a,int b,int c)
{
 int ans=1;
 while(b)
 {
  if(b&1)ans=(ans*a)%c;
  a=(a*a)%c;
  b>>=1;
 }
 if(ans==1)
 return 1;
 else return 0;
}
int main()
{
    int i,j,k,m,n,Euler,ans;
    int q,p,two,T=1,s;
    char ch;
    prime[1]=2;
    prime[2]=3;
    k=2;
    for(i=5;i<=M;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;
    while(scanf("%d%c%d",&p,&ch,&q)!=EOF)
    {two=0;
     p=p/gcd(p,q);q=q/gcd(p,q);
     
     while(q%2==0){two++;q/=2;}
     
     k=0;
     n=m=q;
    for(i=1;i<=prime[0];i++)
    {
     s=0;
     while(n%prime[i]==0){s++;n/=prime[i];}
     if(s>0){k++;p0[k]=prime[i];t[k]=s;}
     if(n==1)break;

     if(n/prime[i]<prime[i]){k++;p0[k]=n;t[k]=1;break;}
   }
    Euler=m;
    for(i=1;i<=k;i++)
    Euler=(Euler/p0[i]*(p0[i]-1));
    n=Euler;
    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;} 
     }
    }
    sort(b,b+k+1);
    for(i=1;i<=k;i++)
    printf("%d\n",b[i]);
    for(i=1;i<=k;i++)
    if(modn(2,b[i],q)){ans=b[i];break;}
    printf("Case #%d: %d,%d\n",T++,two+1,ans);

    }
}

• 哪里来的bg？ (1622) frkstyc 2007-10-06 18:01:04
• Re:按照报告写的还WA,why???? (10) Saerdna 2009-02-25 13:33:49