第三心脏
ty_mxzhn
·
·
题解
我知道你要喷我，但你先别急。
算法 1
使用奇怪枚举方法可以拿到很多分。
算法 2
显然如果 a 是偶数，我们可以通过每次除以 2 将其规约到 a 是奇数的情况。做完这一步就可以拿到 a=2^k 的分了。
算法 3
注意到题目放的视频 MV 是《第三心脏》，所以考虑将 a\oplus b\oplus c 设置为一个定值。（？）
显然不能设置 a\oplus b\oplus c=0，因为这样子怎样都构造不出来的。猜测我们要设计 a\oplus b\oplus c=1。
容易想到令 b=2^p,c=a+b-1。
猜测我们可以构造 d 是偶数，则原式子变为 a^2+b^2+c^2+d^2=(d+1)^2，移项，得到 2d+1=a^2+b^2+c^2。
于是我们要证明的就是 a^2+b^2+c^2 \equiv 1\pmod{4}。（这里是对 4 同余是因为 d 是偶数）
$a\equiv1,3\pmod{4}$，所以 $a^2\equiv 1\pmod{4}$，所以这样做就是对的。
稍微思考一下会发现 $a<b<c<d$ 被自动完成了。
算一下上界吧，可以发现 $d$ 大概可以到 $8\times 10^{18}$ 级别，卡的还是挺紧的。
## 杂项
感谢 not_clever_syl 提供了另一个做法。
关于剩下三个特殊性质。二三个是启发思考的，而且似乎 syl 的做法可以通过这两个特殊性质启发。第四个是构造 $b$ 的时候方便一点。
难度：绿难一点。个人差似乎比较大？ty_ak 说他认为是紫。
## 代码
$a=1$ 的解要找一个。
```cpp
#include <cstdio>
using namespace std;
typedef long long ll;
int a,k;
ll b,c,d;
signed main(){
scanf("%d",&a);
while(!(a&1)) a>>=1,k++;
if(a==1){
b=5,c=7,d=37;
}else{
for(int j=30;j>=0;j--){
if(((a>>j)&1)){
b=(1<<(j+1));
break;
}
}
c=a+b-1;
d=a*c+b*(b-1);
}
b<<=k;
c<<=k;
d<<=k;
printf("%lld %lld %lld\n",b,c,d);
return 0;
}
```