首页 > 代码库 > POJ 3641

POJ 3641

主要是为了试一下MILLER-RABIN的方法

#include <iostream>#include <time.h>#include <cstdio>#include <stdlib.h>#define LL __int64using namespace std;const LL TIME=1000;LL random(LL n){	return (LL)((double)rand()/RAND_MAX*n+0.5);}LL quick(LL a,LL k,LL m){	LL ans=1;	while(k){		if(k&1){			ans=ans*a%m;		}		k>>=1;		a=a*a%m;	}	return ans%m;}bool Miller_Rabin(LL p){	for(LL i=1;i<=TIME;i++){		LL a=random(p-2)+1;		if(quick(a,p-1,p)!=1)		return false;	}	return true;}int main(){	LL p,a;	srand(time(0));	while(scanf("%I64d%I64d",&p,&a),p||a){	//	cout<<p<<a<<endl;		if(Miller_Rabin(p)){			printf("no\n");			continue;		}		bool flag=true;		LL ans=quick(a,p,p);		if(ans==a)printf("yes\n");		else printf("no\n");	}	return 0;}

  

POJ 3641