YTUOJ-Pseudoprime numbers - c++编程基础

Description

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p == a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)

Given 2 < p ≤ 1,000,000,000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a. For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Input

Output

Sample Input

Sample Output

no
no
yes
no
yes
yes

HINT

题意：

给定p，a两个数字2<=p<=1000000000,1

代码如下：

#include 
  
   
#include 
   
     using namespace std; bool isPrime(long long n) { long long i; for (i=2;i<=sqrt(n);i++) { if (n%i==0) return false; } return true; } long long mod(long long a,long long n,long long m) { long long d=1,t=a; while (n>0) //通过n来求a^p%p; { if (n%2==1) //当n为奇数时先乘一个a并%m; d=(d*t)%m; n/=2; t=(t*t)%m; //缩短计算过程 } return d; } int main() { long long a,p; while (cin>>p>>a) { if (a==0&&p==0) break; if (isPrime(p)) cout<<"no"<
    
      运行结果：
     






     ?
     ?
     ?
     ?
     这道题是去年新秀赛的一道英语题，本来昨天晚上就应该完成的，但昨天晚上下雨，为了从机房尽早赶回宿舍测试没通过就没再去考虑它了。今天念了它一天。和同学一交流才发现，英语果然还是硬伤，用上了百度翻译结果还是弄错了题意，p是素数的话应该是输出no，我却认为是输出yes。。。心好累。。。
     ?