专栏文章

第三心脏

tty_mxzhn
P12336题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqtqkcu
此快照首次捕获于
2025/12/04 10:36
3 个月前
此快照最后确认于
2025/12/04 10:36
3 个月前
查看原文
我知道你要喷我，但你先别急。

算法 1

使用奇怪枚举方法可以拿到很多分。

算法 2

显然如果 aa 是偶数，我们可以通过每次除以 22 将其规约到 aa 是奇数的情况。做完这一步就可以拿到 a=2ka=2^k 的分了。

算法 3

注意到题目放的视频 MV 是《第三心脏》，所以考虑将 a⊕b⊕ca\oplus b\oplus c 设置为一个定值。（？）
显然不能设置 a⊕b⊕c=0a\oplus b\oplus c=0，因为这样子怎样都构造不出来的。猜测我们要设计 a⊕b⊕c=1a\oplus b\oplus c=1。
容易想到令 b=2p,c=a+b−1b=2^p,c=a+b-1。
猜测我们可以构造 dd 是偶数，则原式子变为 a2+b2+c2+d2=(d+1)2a^2+b^2+c^2+d^2=(d+1)^2，移项，得到 2d+1=a2+b2+c22d+1=a^2+b^2+c^2。
于是我们要证明的就是 a2+b2+c2≡1(mod4)a^2+b^2+c^2 \equiv 1\pmod{4}。（这里是对 44 同余是因为 dd 是偶数）
b2b^2 不用管，问题在于 a2+c2a^2+c^2，可以化成 a2+(a−1)2a^2+(a-1)^2，那么第二项也不用管，所以只看 a2a^2。
a≡1,3(mod4)a\equiv1,3\pmod{4}，所以 a2≡1(mod4)a^2\equiv 1\pmod{4}，所以这样做就是对的。
稍微思考一下会发现 a<b<c<da<b<c<d 被自动完成了。
算一下上界吧，可以发现 dd 大概可以到 8×10188\times 10^{18} 级别，卡的还是挺紧的。

杂项

感谢 not_clever_syl 提供了另一个做法。
关于剩下三个特殊性质。二三个是启发思考的，而且似乎 syl 的做法可以通过这两个特殊性质启发。第四个是构造 bb 的时候方便一点。
难度：绿难一点。个人差似乎比较大？ty_ak 说他认为是紫。

代码

a=1a=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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...