POJ3641 Pseudoprime numbers

Pが素数でなければap=a(modp)を満たすことができるかどうか
考え方:直接素数判断+高速べき乗型を取ればいいです.私は普通の素数判断を使い始めました.それからmiller_を使いました.rabin改良版の素数テストは、テンプレートにしましょう.
 
AC program:(一般素数判定+高速べき乗)

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int p,a;
bool ispp()
{
  int flag=0; 
  for(int i=2;i*i<=p;i++)
       if(p%i==0)
          {
            flag=1;
            break;       
          }     
  if(!flag)return true;//  
  return false; //  
} 
int fn(int r)
{
  if(r==1)return a%p;
  __int64 tmp=fn(r/2);
  __int64 tmppp=tmp*tmp%p;    
  if(r&1)return tmppp*a%p;
  return tmppp; 
}  
int main()
{
//cout<<fn(2,4)<<endl;
while(cin>>p>>a,p+a)
{
  if(ispp())
    cout<<"no"<<endl;
  else
     {
       if(fn(p)==a)//a^P%p                
          cout<<"yes"<<endl;
       else 
          cout<<"no"<<endl; 
     } 
                      
} 
return 0;} 

 
 
AC program(miller_rabin改良版テスト+高速べき乗)/ただ硬いでしょうテストが運ばれてきて、2つの高速べき乗があります~~囧.もういいから、明日出発するよ~~~がんばろう~~騒年

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<time.h>
#include<algorithm>
using namespace std;
#define Times 12  //miller_rabin  
typedef __int64 LL ; 
int p,a;
LL random(LL n)
{
  return (LL)((double)rand()/RAND_MAX*n+0.5);             
}
LL multi(LL a,LL b,LL m)//a*b%m
{
   LL  ret=0;
   while(b>0)
   {
     if(b&1)
          ret=(ret+a)%m;
     b>>=1;
     a=(a<<1)%m; 
            
               
   }            
   return ret; 
} 
LL quick_mod(LL a, LL b, LL m )
{
  LL ans=1;
  while(b)
  {
    if(b&1)
    {
      ans=multi(ans,a,m);
      b--;       
    }     
    b/=2;
    a=multi(a,a,m);   
  }
  return ans;                
} 
bool witness(LL a,LL n)
{
   int m=n-1;
   int j=0;
   while(!(m&1))
   {
     j++;
     m>>=1;             
   }     
   LL x=quick_mod(a,m,n);
   if(x==1||x==n-1)
     return false;
   while(j--)
   {
     x=x*x%n;
     if(x==n-1)
         return false;          
   } 
   return true; 
} 
bool miller_rabin(LL n) 
{
  if(n<2)return false;
  if(n==2)return true;
  if(!(n&1))return false;
  for(int i=1;i<=Times;i++)
  {
    LL a=random(n-2)+1;
    if(witness(a,n))return false;      
  } 
  return true;    
} 
int fn(int r)
{
  if(r==1)return a%p;
  __int64 tmp=fn(r/2);
  __int64 tmppp=tmp*tmp%p;    
  if(r&1)return tmppp*a%p;
  return tmppp; 
}  
int main()
{
//cout<<fn(2,4)<<endl;
while(cin>>p>>a,p+a)
{
  if(miller_rabin(p))
    cout<<"no"<<endl;
  else
     {
       if(fn(p)==a)//a^P%p                
          cout<<"yes"<<endl;
       else 
          cout<<"no"<<endl; 
     } 
                      
} 
return 0;}