题解 [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 直到解合法即可。

现在我们来考虑如何不随机化。

考虑钦定 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，则此时一定有解。

首先给出结论：

• 首先判掉 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 分别为奇数和偶数的两种情况拼起来即可。

代码：

#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;
}