YTUOJ-Pseudoprime numbers

YTUOJ-Pseudoprime numbers

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

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

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。。。心好累。。。