POJ 3641 Pseudoprime numbers

ゝ一纸荒年。 2022-06-01 07:49 163阅读 0赞

###  ###

Pseudoprime numbers

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;11784</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;5053</td> 
  </tr> 
 </tbody> 
</table>

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

Source

[Waterloo Local Contest][], 2007.9.23

###  ###

费马定理指出，对于任意的素数 *p* 和任意的整数 *a* > 1，满足 *ap* = *a* (mod *p*) 。也就是说，*a* 的 *p* 次幂除以 *p* 的余数等于 *a* 。*p* 的某些 (但不是很多) 非素数的值，被称之为以 *a* 为底的伪素数，对于某个 *a* 具有该特性。并且，某些 Carmichael 数，对于全部的 *a* 来说，是以 *a* 为底的伪素数。

给定 2 < *p* ≤ 1000000000 且 1 < *a* < *p* ，判断 *p* 是否为以 *a* 为底的伪素数。

输入

输入包含多个测试用例，以 "0 0" 表示输入结束。每个测试用例，由包含 *p* 和 *a* 的一行组成。

输出

对于每个测试用例，如果 p 是以 *a* 为底的伪素数，则输出 "yes"，否则输出 "no" 。

### [http://poj.org/problem?id=3641][http_poj.org_problem_id_3641] ###

第一次做的时候用的是int 没有用long long 范围比较小，出错了

而且英文题目，还扯了费马小定理，百度了一下，但是也没用到

写两个函数就行了，快速幂，素数判断

/*
    	题意：
    	判断P是否为素数，是即输出no
    	不是就计算a的p次方是否等于a，是就输出yes，否则输出no；
    */
    
    
    /*
    	这个题要求 求出若p不是素数并且p^a是否等于a，若等于则输出yes,否则输出no
    
    */
    
    #include<stdio.h>
    #include<string.h>
    #define LL long long
    LL int prime(LL int a)
    {
    	int z=1;
    	if(a<2)	return 0;
    	for(int i=2;i*i<=a;i++)
    	{
    		if(a%i==0)
    		{
    			z=0;
    			break;
    		}
    	}
    	return z;
    }
    LL int pow_mod(LL int a,LL int b,LL int c)
    {
    	LL int ans=1;
    	while(b)
    	{
    		if(b&1)	ans=ans*a%c;
    		a=a*a%c;
    		b>>=1;
    	}
    	return ans;	
    }
    int main()
    {
    	LL int p,a;
    	while(scanf("%lld %lld",&p,&a)!=EOF)
    	{
    		if(p==0&&a==0)	break;
    		if(prime(p))	printf("no\n");
    		else if(pow_mod(a,p,p)==a)	printf("yes\n");
    		else printf("no\n");
    		
    	 } 
    	return 0;
    }

现在看看原来写的代码发现好啰嗦啊。。。

现在的代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    ll gcd(ll a,ll b)
    {
    	return !b?a:gcd(b,a%b);
    }
    ll pow_mod(ll a,ll b,ll c)//快速幂 
    {
    	ll ans=1;
    	a=a%c; 
    	while(b)
    	{
    		if(b&1)	ans=ans*a%c;
    		a=a*a%c;
    		b>>=1;
    	}
    	return ans;
    }
    ll prime(ll n)//判断素数 
    {
    	for(int i=2;i<=sqrt(n);i++)
    		if(n%i==0)	return 0;
    	return n>1;	
    }
    int main()
    {
    	ll p,a;
    	while(~scanf("%lld %lld",&p,&a)&&(p|a))
    	{
    		if(!prime(p)&&pow_mod(a,p,p)==a)	printf("yes\n");
    		else	printf("no\n");
    	 } 
    	return 0;
    }

[Waterloo Local Contest]: http://poj.org/searchproblem?field=source&key=Waterloo+Local+Contest
[http_poj.org_problem_id_3641]: http://poj.org/problem?id=3641