POJ 3641 Pseudoprime numbers 伪素数测试

本文主要是介绍POJ 3641 Pseudoprime numbers 伪素数测试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：判断一个数是否是基于a的伪素数。只有当p是合数且a^p = a ( mod p ) 时，才输出yes。

题解：Miller_Rabin素数测试。

#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
#define lint __int64lint modular_exponent ( lint a, lint b, lint n )
{lint ret = 1;for ( ; b; b >>= 1, a = a*a%n )if ( b & 1 )ret = ret * a % n;return ret;
}int miller_rabin ( int n, int time = 20 )
{if ( n==1 || (n!=2&&!(n%2)) || (n!=3&&!(n%3)) || (n!=5&&!(n%5)) || (n!=7&&!(n%7)) )return 0;while ( time-- ){lint m = modular_exponent ( rand()%(n-1) + 1, n-1, n );if ( m != 1 ) return 0;}return 1;
}int main()
{lint p, a;while ( 1 ){scanf("%I64d%I64d",&p,&a);if ( a == 0 && p == 0 ) break;if ( modular_exponent(a,p,p) == a && !miller_rabin(p) )printf("yes\n");else printf("no\n");}return 0;
}

这篇关于POJ 3641 Pseudoprime numbers 伪素数测试的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---