1905.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 38 行

#include<stdio.h>
#include<math.h>
int prime(__int64 n){
    __int64 t=sqrt(double(n));
    if(n==2)    return 1;
    for(__int64 i=3;i<=t;i+=2)
        if(n%i==0)  return 0;
    return 1;
}
__int64 pow_mod(__int64 a,__int64 p,__int64 n){
    __int64 k=1;
    while(p>1){
        if(p%2==1)  k=a*k%n;
        a=a*a%n;
        p/=2;
    }
    return a*k%n;
}
int main()
{
    __int64 p,a;
    while(scanf("%I64d%I64d",&p,&a)==2){
        if(p==0&&a==0)
            break;
        if(prime(p)==1){
            printf("no\n");
            continue;
        }
        __int64 t=p;
        __int64 x=1,y=a,n=0;
        if(pow_mod(a,p,t)==a)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}