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

题意：

给定p和a，判断p是不是以a为基础的伪素数 即不是素数，但满足以a为底数时的费马小定理公式ap≡a (mod p)" role="presentation">ap≡a (mod p)$a^p\equiv a(modp)$

分析：

直接快速幂取模判断是否满足上面式子，且不是素数则是伪素数 如果知道费马小定理的人都知道费马小定理的公式其实是写成 ap−1≡1 (mod p)" role="presentation">ap−1≡1 (mod p)$a^{p-1}\equiv 1(modp)$ 但是不能用这个式子判断是否满足，wa了 满足这个式子需要一个条件那就是p不能整除a 但是题目告诉了a < p所以我也不知道为什么了。。。希望有大佬解释一下 两面同乘a是为了得到一个对所有整数a都成立的陈述，这种形式使用起来更加方便 题目也给的第一个式子那就用第一个式子判断吧。。 code： #include #include #include #include using namespace std; typedef long long ll; const int S = 8; ll mul_mod(ll a,ll b,ll mod){ a %= mod; b %= mod; ll ans = 0; while(b){ if(b & 1){ ans += a; if(ans >= mod) ans -= mod; } a <<= 1; if(a >= mod) a -= mod; b >>= 1; } return ans; } ll q_pow(ll a,ll b,ll mod){ ll ans = 1; a %= mod; while(b){ if(b & 1){ ans = mul_mod(ans,a,mod); } a = mul_mod(a,a,mod); b >>= 1; } return ans; } bool check(ll a,ll n,ll x,ll t){ ll ret = q_pow(a,x,n); ll last = ret; for(int i = 1; i <= t; i++){ ret = mul_mod(ret,ret,n); if(ret == 1 && last != 1 && last != n-1) return true; last = ret; } if(ret != 1) return true; return false; } bool Miller_Rabin(ll n){ if(n < 2) return false; if(n == 2) return true; if((n & 1) == 0) return false; ll x = n - 1; ll t = 0; while((x & 1) == 0){ x >>= 1; t++; } for(int i = 0; i < S; i++){ ll a = rand() % (n-1) + 1; if(check(a,n,x,t)) return false; } return true; } int main(){ ll p,a; while(scanf("%lld%lld",&p,&a) != EOF){ if(p == 0 && a == 0) break; if(q_pow(a,p,p) == a && !Miller_Rabin(p)){ printf("yes "); } else printf("no "); } return 0; }