POJ 3641 Pseudoprime numbers(高速べき乗、素性テスト)

Pseudoprime numbers
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 7076
 
Accepted: 2900
Description
Fermat's theorem states that for any prime number p and for any integer a > 1, ap = 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 ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.
Input
Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.
Output
For each test case, output "yes"if p is a base-a pseudoprime; otherwise output "no".
Sample Input

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

Sample Output

no
no
yes
no
yes
yes

2つの条件は素数がFermat little Theoremを満たすことではない
MACコードは以下の通りである.

//
//  POJ 3641 Pseudoprime numbers
//
//  Created by TaoSama on 2015-03-23
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#define CLR(x,y) memset(x, y, sizeof(x))

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

long long n, m;
long long ksm(long long x, long long n, long long m) {
    long long ret = 1;
    while(n) {
        if(n & 1) ret = ret * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return ret;
}

bool is_prime(int n) {
    for(int i = 2; i * i <= n; ++i)
        if(n % i == 0) return false;
    return true;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//	freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> m >> n && n && m) {
        if(!is_prime(m) && ksm(n, m, m) == n)
            cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}