正文
poj Pseudoprime numbers 3641
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Pseudoprime numbers
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 10903 | Accepted: 4710 |
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 p th 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 题意：判断伪质数，即非质数，并且满足:存在a,使得a^p==a mod(p)的p称为伪质数。
思路：快速幂运算验证即可。
AC代码：
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define MOD 1000000000
typedef long long ll;
const int N_MAX = ;
ll p, a;
ll ll_mult(ll a,ll x,ll p) {
ll res = ; bitset<>tmp = static_cast<bitset<>>(x);//前面低位
for (int i = ; i < tmp.size();i++) {
if (tmp[i])res += a*( << i);
res %= p;
} return res;
} ll mod_pow(ll x,ll n,ll p) {
ll res = ;
while (n) {
if (n & )res = ll_mult(res,x,p);
x = ll_mult(x, x,p);
n >>= ;
}
return res;
} bool is_prime(ll n) {
for (int i = ; i*i <= n;i++) {
if (n%i == )return false;
}
return n!=;
} int main() {
while (scanf("%lld%lld",&p,&a)&&(p||a)) {
if (is_prime(p)) { puts("no"); continue; }
if (mod_pow(a, p, p) == a)puts("yes");
else puts("no");
} return ;
}
