题意 给出两个数字 P 和 A 当p 不是素数 并且 满足a^p≡a(mod p) 就输出 yes 否则 输出 no
思路 因为 数据范围较大，用快速幂
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <iostream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; LL powerMod(LL x, LL n, LL m) { LL res = 1; while (n > 0) { if (n & 1) res = (res * x) % m; x = (x * x ) % m; n >>= 1; } return res; } bool isPrime(int x) { int flag; int n, m; if (x <= 1) return false; if (x == 2 || x == 3) return true; if (x % 2 == 0) return false; else { m = sqrt(x) + 1; for (n = 3; n <= m; n += 2) { if (x % n == 0) { return false; } } return true; } } int main() { LL p, a; while (cin >> p >> a && (p || a)) { if (powerMod(a, p, p) == a && a % p == a && isPrime(p) == false) cout << "yes\n"; else cout << "no\n"; } }转载于:https://www.cnblogs.com/Dup4/p/9433275.html
