题解 [ARC158D] Equation

下面 $x, y, z$ 无序。 首先是赛时想法： - 打表发现一定存在一组解使得 $x + y = p$。 - 当 $n$ 为偶数，设 $r = \frac{x}{z}$，则 $z = \frac{2r^{3n} + 1}{(2r^n + 1)(2r^{2n} + 1)}$；当 $n$ 为奇数，同样设 $r = \frac{x}{z}$，则 $z = \frac{1}{2r^{2n} + 1}$。 - 随机化 $r$ 直到解合法即可。 现在我们来考虑如何不随机化。 1. $n$ 为奇数 考虑钦定 $r = 2$，但是你会发现有时候 $2^{2n} \equiv -\frac{1}{2} \pmod p$ 导致无解。 考虑在无解时改 $r = 2$ 为 $r = 4$，由于 $4^{2n} \equiv \frac{1}{4} \not\equiv -\frac{1}{2} \equiv 2^{2n} \pmod p$，则此时一定有解。 2. $n$ 为偶数 首先给出结论： - 首先判掉 $p = 5, 11$ 的情况。 - 令 $r = 2$，每次按照前述方法求出对应的 $x, y, z$，如果解不合法则令 $r \leftarrow r^2$ 并继续。 - 可以证明一定有解，且尝试的 $r$ 的个数 $\leq 3$。 证明：首先，失败只可能有两种情况 $z$ 的某个分子或分母为 $0$ 或 $r = p - 1$。 对于第二种情况，由于 $r$ 可以表示成 $2^{2^k}$ 的形式，则 $p$ 此时只可能为费马质数。对三个需要检验的费马质数 $17, 257, 65537$ 进行了验证，均满足上述条件。 对于第一种情况，考虑在失败时分类讨论 $2r^n + 1, 2r^{2n} + 1, 2r^{3n} + 1$ 中哪个为 $0$。下面设 $r' = r^2$。 - $2r^n + 1 = 0$ 于是有 $(r')^n \equiv \frac{1}{4} \pmod p$，则 $2(r')^n + 1 \equiv \frac{3}{2} \not\equiv 0 \pmod p$，$2(r')^{2n} + 1 \equiv \frac{5}{4} \not\equiv 0 \pmod p$（注意我们判掉了 $p = 5$），$2(r')^{3n} + 1 \equiv \frac{33}{32} \not\equiv 0 \pmod p$（注意我们判掉了 $p = 11$）。于是自乘一次后一定合法。 - $2r^{2n} + 1 = 0$ 于是有 $(r')^{2n} \equiv \frac{1}{4} \pmod p$，则 $2(r')^{2n} + 1 \equiv \frac{3}{2} \not\equiv 0 \pmod p$；因为 $(r')^n \equiv \pm \frac{1}{2} \pmod p$，则 $2(r')^n + 1 \equiv 0 \operatorname{or} 2 \pmod p$，$2(r')^{3n} + 1 \equiv \frac{3}{4} \operatorname{or} \frac{5}{4} \not\equiv 0 \pmod p$。于是自乘一次后要么合法，要么转化为 $2r^n + 1 = 0$ 的情况。 - $2r^{3n} + 1 = 0$ 于是有 $(r')^{3n} \equiv \frac{1}{4} \pmod p$，则 $2(r')^{3n} + 1 \equiv \frac{3}{2} \not\equiv 0 \pmod p$；假定 $(r')^n = -\frac{1}{2}$，则 $(r')^{3n} \equiv -\frac{1}{8} \not\equiv \frac{1}{4} \pmod p$；假定 $(r')^{2n} = -\frac{1}{2}$，则 $(r')^{6n} \equiv -\frac{1}{8} \not\equiv \frac{1}{16} \pmod p$。于是自乘一次后一定合法。 综上，把 $n$ 分别为奇数和偶数的两种情况拼起来即可。 代码： ```cpp #include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll ans[7]; inline ll quick_pow(ll x, ll p, ll mod){ ll ans = 1; while (p){ if (p & 1) ans = ans * x % mod; x = x * x % mod; p >>= 1; } return ans; } inline bool check(){ sort(ans + 1, ans + 4); return ans[1] != ans[2] && ans[2] != ans[3]; } int main(){ int t; cin >> t; for (int i = 1; i <= t; i++){ int n, p; cin >> n >> p; n %= p - 1; if (n % 2 == 0){ if (p == 5 || p == 11){ for (int j = 2; ; j++){ ans[1] = (quick_pow(j, (ll)n * 3, p) * 2 % p + 1) % p * quick_pow((quick_pow(j, n, p) * 2 % p + 1) % p * (quick_pow(j, n * 2, p) * 2 % p + 1) % p, p - 2, p) % p; ans[2] = ans[1] * j % p; ans[3] = p - ans[2]; if (check()) break; } } else { ll r = 2; do { ans[1] = (quick_pow(r, (ll)n * 3, p) * 2 % p + 1) % p * quick_pow((quick_pow(r, n, p) * 2 % p + 1) % p * (quick_pow(r, n * 2, p) * 2 % p + 1) % p, p - 2, p) % p; ans[2] = ans[1] * r % p; ans[3] = p - ans[2]; r = r * r % p; } while (!check()); } } else { ans[1] = quick_pow((quick_pow(2, n * 2, p) * 2 % p + 1) % p, p - 2, p); if (ans[1] == 0){ ans[1] = quick_pow((quick_pow(4, n * 2, p) * 2 % p + 1) % p, p - 2, p); ans[2] = ans[1] * 4 % p; } else { ans[2] = ans[1] * 2 % p; } ans[3] = p - ans[2]; check(); } for (int j = 1; j <= 3; j++){ cout << ans[j] << " "; } cout << endl; } return 0; } ```