首页 > 程序开发 > 软件开发 > 其他 >

HPUOJ 伪素数

2017-02-23

HPUOJ 伪素数:HPUOJ 伪素数又该怎么解答呢?希望下面的文章对大家有所帮助。

HPUOJ 伪素数:HPUOJ 伪素数又该怎么解答呢?希望下面的文章对大家有所帮助。
思路:(1):p是非素数。
      (2):a的p次方对p取余不等于a.
#include typedef long long LL; LL Quick_MI(LL a,LL b,LL c) { int s=1; a=a%c; while(b) { if(b&1) { s=(s*a)%c; } a=(a*a)%c; b=b/2; } return s; //快速幂 } typedef long long LL; LL SS (LL x) { long long i; for(i=2;i*i<=x;i++) { if(x%i==0) return 0; } return 1; } //素数判断 int main() { long long p,a,k; while(scanf("%lld%lld",&p,&a),p||a) { k=Quick_MI(a,p,p); if((!SS(p))&&k==a) { printf("yes\n"); } else printf("no\n"); } return 0; }

相关文章
最新文章
热点推荐