题意:判断一个数是否是基于a的伪素数。只有当p是合数且a^p = a ( mod p ) 时,才输出yes。
题解:Miller_Rabin素数测试。
#include<cstdio> #include<ctime> #include<cstdlib> using namespace std; #define lint __int64 lint 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; }