自动搬运

查看原文

来自洛谷，原作者为

	寄风 现实中的你，是否很成功？

搬运于2025-08-24 23:14:43，当前版本为作者最后更新于2025-04-25 21:02:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd on 2025.6.5 修正了一个笔误，感谢

场切并获得了首 A。

挺好的锻炼脑力题。

考虑推一个柿子，那么：

$$\sqrt{a^2+b^2+c^2+d^2}=a\oplus b\oplus c\oplus d$$ $$a^2+b^2+c^2+d^2=(a\oplus b\oplus c\oplus d)^2$$

因为 $\forall{x>0},x^2>0$，所以 $(a\oplus b\oplus c\oplus d)>d$。

令 $(a\oplus b\oplus c\oplus d)=d+x$。

那么我们考虑把柿子拆开：

$$a^2+b^2+c^2+d^2=(d+x)^2$$ $$a^2+b^2+c^2+d^2=d^2+2\times x\times d+x^2$$ $$a^2+b^2+c^2=2\times x\times d+x^2$$

获得了这个之后我们该怎么做？

首先任意一个 $x$ 我们都可以构造，设 $\log_{2}(x)+1=y$，那么我们让 $d$ 的后 $y$ 位都是 $0$，然后 $a\oplus b\oplus c$ 就是 $x$ 就可以了。

那么你发现 $x$ 越小构造难度应该也是越小的。

那么先令 $x=0$，那么 $a^2+b^2+c^2=0$，显然是不可以的。

那么考虑让 $x=1$。

那么我们获得了两个条件，就是 $a\oplus b\oplus c=1$ 和 $a^2+b^2+c^2=2\times d+1$；同时我们还获得了一个约束，就是 $d \bmod 2$ 必须是 $0$。

保险起见，我们先把 $a=1$ 判掉，这个直接写个暴力找解即可。

那么因为 $a\oplus b\oplus c=1$，$a$ 又大于 $1$，所以如果 $a$ 的最高位和 $b,c$ 的最高位相同我们是不好构造的。所以我们只能考虑从比 $a$ 的最高位更高的位入手，设 $a$ 的最高位是第 $q$ 位，那么 $b$ 和 $c$ 的第 $q+1$ 位都是 $1$ 就可以了。

然后因为我们要保证 $a<b<c$，所以我们考虑将 $b$ 的第 $q$ 位置为 $0$，将 $c$ 的第 $q$ 位置为 $1$ 就可以了。

那么剩下的位的话，因为二进制的按位考虑，所以我们可以将 $b$ 的第 $0$ 位到第 $q-1$ 位都设成和 $a$ 一样，这样子 $a\oplus b$ 就是 $2^q+2^{q+1}$ 了。

那么我们再将 $c$ 的第 $0$ 位置 $1$ 就可以满足 $a\oplus b\oplus c=1$ 了。

$d$ 的求法就是 $d=\frac{a^2+b^2+c^2-1}{2}$。

这显然满足 $c<d$。

总结下，就是构造 $b=a+2^q,c=2^{q+1}+2^q+1$ 即可。

那么看上去对完了？这真的是对的吗？

这个正确性非常显然，用屁股都能想到。

写一发，结果。

其实这个做法是错的。

为啥会错呢？我们发现我们上面推导的一切，都有一个前提：$d \bmod 2$ 必须是 $0$。而我们上面并没有保证 $d \bmod 2$ 是 $0$。

难道我们的努力白费了？

并不是。

我们考虑 $d \bmod 2$ 是 $0$ 的限制，也就是说 $d^2 \bmod 4$ 必须是 $0$，也就是说 $d^2 \bmod 4+1$ 必须是 $1$。

在我们上面的构造中，我们保证了 $b \equiv a \pmod 2$ 和 $c \bmod 2=1$。

所以如果 $a \bmod 2=0$，那么带回原式，我们的构造是有效的，$a^2\bmod 4=0$，$b^2\bmod 4=0$，$c^2\bmod 4=1$，$a^2+b^2+c^2 \equiv 2\times d+1 \pmod 4$。

但是如果 $a \bmod 2=1$ 我们的构造就无效了。

考虑将 $b$ 与 $c$ 进行微调，由于 $a \bmod 2=1$，所以如果我们将 $b$ 和 $c$ 的值同时减小 $1$ 的话，并不会影响 $a\oplus b\oplus c$ 的结果。

重新带回，当 $a \bmod 2=1$ 时，$a^2\bmod 4=1$，$b^2\bmod 4=0$，$c^2\bmod 4=0$，$a^2+b^2+c^2 \equiv 2\times d+1 \pmod 4$。

那么就做完了，不难证明大小关系依然满足 $a<b<c<d$。

代码：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i128 = __int128;
using u128 = unsigned __int128;

i64 a, b, c, d;

inline void debug() {
    std::cerr << "check:\n";

    std::cerr << a * a + b * b + c * c + d * d << '\n';

    std::cerr << (a ^ b ^ c ^ d) * (a ^ b ^ c ^ d) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    std::cin >> a;

    if (a == 1) {
        for (int b = a + 1; b <= 500; b++) {
            for (int c = b + 1; c <= 500; c++) {
                for (int d = c + 1; d <= 500; d++) {
                    int xx = (a ^ b ^ c ^ d);
                    if (a * a + b * b + c * c + d * d == xx * xx) {
                        std::cout << b << ' ' << c << ' ' << d << '\n';
                        return 0;
                    }
                }
            }
        }
        std::cout << -1 << '\n';
        return 0;
    }

    //b=a+(1<<q),c=(1<<(q+1))+(1<<q)+1
    
    int q = std::__lg(a);

    if (a % 2 == 0) {
        b = a + (1ll << q), c = (1ll << (q + 1)) + (1ll << q) + 1;

        d = (a * a + b * b + c * c - 1) / 2;
        //我靠，要保证 d 最后一位是 0

        if (d % 2 == 0) {
            std::cout << b << ' ' << c << ' ' << d << '\n';
            debug();
            return 0;
        } 
        assert(0);
    } else {
        b = a + (1ll << q) - 1, c = (1ll << (q + 1)) + (1ll << q);

        d = (a * a + b * b + c * c - 1) / 2;
        //我靠，要保证 d 最后一位是 0

        if (d % 2 == 0) {
            std::cout << b << ' ' << c << ' ' << d << '\n';
            debug();
            return 0;
        } 
        exit(114);
    }

    // for (int d = c + 1; d <= 100000; d++) {
    //     int xx = (a ^ b ^ c ^ d);
    //     if (a * a + b * b + c * c + d * d == xx * xx) {
    //         std::cout << d << '\n';
    //         return 0;
    //     }
    //     std::cerr << a * a + b * b + c * c + d * d << " " << xx * xx << '\n';
    // }

    // std::cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';

    // std::cerr << (a ^ b ^ c) << ' ' << a * a + b * b + c * c << '\n';

    return 0;
}

有心路历程的代码，大家可以看看我赛时心态。