首页 > 代码库 > HDU 2138

HDU 2138

这题用MILLER测试应该是不可避免的。

#include <iostream>#include <cstdio>#include <stdlib.h>#include <time.h>#define LL __int64using namespace std;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;}bool judgep(LL p){	for(int i=1;i<=15;i++){		LL a=random(p-2)+1;		if(quick(a,p,p)!=a)		return false;	}	return true;}int main(){	int n;	LL p;	srand(time(0));	while(scanf("%d",&n)!=EOF){		int flag=0;		for(int i=1;i<=n;i++){			scanf("%I64d",&p);			if(judgep(p)){				flag++;			}		}		printf("%d\n",flag);	}	return 0;}

  

HDU 2138