Q1: 为什么要随机质数
A1: 因为不随机可能会被 hack
Q2: 为什么要编译期生成
A2: 编译期生成的话，编译器可以上取模常数优化
Q3: 你咋搞的
A3: __TIME__ __TIMESTAMP__ 这两个宏。
具体来说，每次编译后，生成的质数相同。重新编译后，生成的质数不同。
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using u128 = __int128;
constexpr ll pow(ll a, ll x, ll p, ll res = 1) {
for(;x;x >>= 1, a = (u128) a * a % p)
if(x & 1) res = (u128) res * a % p;
return res;
}
constexpr bool checkprime(ll p) {
if(p == 1) return 0;
ll d = __builtin_ctzll(p - 1), s = (p - 1) >> d;
for(ll a : {2, 3, 5, 7, 11, 13, 82, 373}) {
if(a % p == 0)
continue;
ll x = pow(a, s, p), y = 0;
for(int i = 0;i < d;++i, x = y) {
y = (u128) x * x % p;
if(y == 1 && x != 1 && x != p - 1) return 0;
}
if(x != 1) return 0;
}
return 1;
}
constexpr ll gen_prime(ll L, ll R) {
// gen prime in [L, R)
u64 x = 1128471;
for(char c : __TIME__ __TIMESTAMP__) {
x += c, x ^= x << 13, x ^= x >> 7, x ^= x << 17;
}
for(;;) {
x ^= x << 13, x ^= x >> 7, x ^= x << 17;
ll y = L + x % (R - L);
if(checkprime(y))
return y;
}
return 0;
}
constexpr ll mod = gen_prime(1e17, 1e18);
int main() {
cout << mod << '\n';
}