题解：P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

diqiuyi · 2024-09-10 07:55:33 · 题解

神秘构造。

这个限制看上去比较松，所以不妨令 b=1。此时只要 \operatorname{lcm}(c,d)=a+c+d。

考虑 a 为奇数如何处理，发现 c=2，d=a+2 可以满足。

考虑 a=4k+2，发现 c=4，d=a+4 可以满足。

记 v 为满足 2^v\mid a 的最大整数，注意到 c=2^{v+1}，d=2^{v+1}+a 可以满足。此时 \gcd(c,d)=\gcd(c,a)=2^v，所以 \operatorname{lcm}(c,d)=2^{v+2}+2a=a+c+d，符合要求。

因为 a\le 10^9，所以 v\le 29。

若 v\le28，$d\le 10^9+2^{29}=1536870912