Pseudoprime numbers POJ - 3641(快速幂)

喜欢ヅ旅行 2022-02-20 16:19 170阅读 0赞

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 *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

解题思路:

数据量较大,这里得用快速幂算法

这题不能用筛法提前打表(会超时),对于每一个p,直接判断是否是素数就可以了,不会超时

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <algorithm>
    #include <math.h>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    typedef long long ll;
    ll p, a;
    bool is_prime(long long n)
    {
    	for (long long i = 2; i <= sqrt(1.0*n); i++)
    	{
    		if (n%i == 0)
    		{
    			return false;
    		}
    	}
    	return true;
    }
    
    //快速幂
    ll smPow_Mod(ll a, ll b, ll mod) {
    	ll mres = 1, mtemp = a;
    	for (; b; b /= 2) {
    		if (b & 1) {
    			mres = mres * mtemp % mod;
    		}
    		mtemp = mtemp * mtemp % mod;
    	}
    	return mres;  //返回值
    }
    
    int main() {
    	while (scanf("%lld %lld", &p, &a) != EOF) {
    	      if(p == 0 && a == 0) break;
    		  
    		  if (!is_prime(p) && smPow_Mod(a, p, p) == a % p) {
    			  printf("yes\n");
    		  }
    		  else {
    			  printf("no\n");
    		  }
    
    	}
    	system("PAUSE");
    	return 0;
    }