poj3641

問題はpを入力することを意味して、mはpが素数の出力noならばさもなくばmのp次方%pがmに等しいかどうかを見て、高速べき乗で型を取って、復習します

#include <stdio.h>
#include <math.h>
__int64 modular(__int64 a,__int64 b,__int64 c)//     (a b    c)
{
    __int64 ans=1;
    a=a%c;
    while(b>0)
    {
        if ((b&1)==1)//     
 		ans=(ans*a)%c;//        
 		b>>=1;//b=b/2;
 		a=(a*a)%c;
    }
   return ans;
}
int isprime(__int64 x)
{
    __int64 i,j,k=(int)sqrt(x);
    if ((x==2)||(x==3))
    return 1;
    if (x==0)
    return 0;
    for (i=2;i<=k;i++)
    if (x%i==0)
    return 0;
    return 1;
}
 int main()
 {
     __int64 p,m,result;
     while(scanf("%I64d%I64d",&p,&m)==2)
     {
         if ((p==0)&&(m==0))
            break;
         if (isprime(p))
            printf("no
");
         else
            {
            if (modular(m,p,p)==m)
              printf("yes
");
            else
              printf("no
");
            }
      }
      return 0;
}

//        
__int64 modular(__int64 a,__int64 b,__int64 c)//     (a b    c)
{
    __int64 ans=1;
    a=a%c;
    while(b>0)
    {
        if ((b&1)==1)//     
 		ans=(ans*a)%c;//        
 		b>>=1;//b=b/2;
 		a=(a*a)%c;
    }
   return ans;
}