Pseudoprime numbers
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
Source
Waterloo Local Contest, 2007.9.23
题目类型：伪素数测试
算法分析：按照以a为基的伪素数的定义判断即可，也就是判断是否p为合数，且对于任意的正整数a，满足a ^ p = a (mod p)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 10000 + 66; const int testnum = 8; //随机算法判定次数，一般8~10就够了 // 计算ret = (a*b)%c a,b,c < 2^63 long long mult_mod (long long a,long long b,long long mod) { a %= mod; b %= mod; long long ans = 0; long long temp = a; while (b) { if (b & 1) { ans += temp; if (ans > mod) ans -= mod;//直接取模慢很多 } temp <<= 1; if (temp > mod) temp -= mod; b >>= 1; } return ans; } long long pow_mod (long long a,long long n,long long mod) { long long ans = 1; long long temp = a % mod; while (n) { if (n & 1) ans = mult_mod (ans, temp, mod); temp = mult_mod (temp, temp, mod); n >>= 1; } return ans; } bool IsPrime (long long val) { if (val == 1 || val == 2) return true; for (long long i = 2; i * i <= val; i++) if (val % i == 0) return false; return true; } int main() { // ifstream cin ("aaa.txt"); long long a, p; while (cin >> p >> a) { if (a == 0 && p == 0) break; if (IsPrime (p)) cout << "no" << endl; else { long long ans = pow_mod (a, p, p); if (ans == a) cout << "yes" << endl; else cout << "no" << endl; } } return 0; } |
- « 上一篇：poj3468
- poj3646：下一篇 »