快速幂和判断素数。题意:如果a^p mod p = a mod p且p不为素数,那么称p为基于a的伪素数,现在给你p和a,问p是不是基于a的伪素数。
我的解题思路:很简单,判断一下p是否为素数,然后快速幂求a^p mod p的值就行了,由于a比p小,所以a mod p肯定还是a,就不用判断是否等于a mod p了,另外必须要用64位整型,不然会溢出。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; typedef long long Long; Long a, p; bool IsPrime(Long x); Long FastPow(Long base, Long n, Long mod); int main() { while (~scanf("%lld %lld", &p, &a) && a && p) { if (!IsPrime(p) && FastPow(a, p, p) == a) { puts("yes"); } else { puts("no"); } } return 0; } bool IsPrime(Long x) { Long cnt = (Long)sqrt(x + 0.5) + 1; for (Long i=2; i<cnt; ++i) { if (x % i == 0) return false; } return x == 1 ? false : true; } Long FastPow(Long base, Long n, Long mod) { Long ans = 1; base %= mod; while (n) { if (n & 1) { ans *= base; ans %= mod; } base *= base; base %= mod; n >>= 1; } return ans; }