constint N = 5; // 测试次数 longlongrandom(longlong n) { return (longlong)((double)rand() / RAND_MAX * n + 0.5); } longlongmulti(longlong a, longlong b, longlong m)// a * b % m { longlong ret = 0; while (b) { if (b & 1) ret = (ret + a) % m; b >>= 1; a = (a << 1) % m; } return ret; } longlongquick_mod(longlong a, longlong b, longlong m) { longlong ans = 1; while (b) { if (b & 1) ans = multi(ans, a, m); b >>= 1; a = multi(a, a, m); } return ans; } boolmiller_rabin(longlong n) { if (n == 2) returntrue; if (n < 2 || !(n & 1)) returnfalse; for (int i = 1; i <= N; ++i) { longlong a = random(n - 2) + 1; if (quick_mod(a, n - 1, n) != 1) returnfalse; } returntrue; }
constint N = 5; // 测试次数 longlongrandom(longlong n) { return (longlong)((double)rand() / RAND_MAX * n + 0.5); } longlongmulti(longlong a, longlong b, longlong m)// a * b % m { longlong ret = 0; while (b) { if (b & 1) ret = (ret + a) % m; b >>= 1; a = (a << 1) % m; } return ret; } longlongquick_mod(longlong a, longlong b, longlong m) { longlong ans = 1; while (b) { if (b & 1) ans = multi(ans, a, m); b >>= 1; a = multi(a, a, m); } return ans; } boolWitness(longlong a, longlong n) { longlong m = n - 1; int j = 0; while (!(m & 1)) { ++j; m >>= 1; } longlong x = quick_mod(a, m, n); if (x == 1 || x == n - 1) returnfalse; while (j--) { x = x * x % n; if (x == n - 1) returnfalse; } returntrue; } boolmiller_rabin(longlong n) { if (n == 2) returntrue; if (n < 2 || !(n & 1)) returnfalse; for (int i = 1; i <= N; ++i) { longlong a = random(n - 2) + 1; if (Witness(a, n)) returnfalse; } returntrue; }