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

· · 题解

题目大意

给定正整数 a，找到一组正整数 b,c,d 使得 a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)。

解题思路

一、打表找规律

前四组答案可以为：

a b c d
1 1 2 3
2 1 4 6
3 1 2 5
4 1 8 12

注意到 b=1,d=a+c。
要找 a,c 的关系，可以转成二进制看：

a b c d
1 1 10 11
10 1 100 110
11 1 10 101
100 1 1000 1100

注意到 c 等于 a 的最右边的 1 所代表的值 \times2，即 c=\operatorname{lowbit}(a)\times2，lowbit(a)=a&-a，不知道 lowbit 的点这里。

二、证明

以下设 \operatorname{lowbit}(a)=2^k。

a+b+c+d=a+1+2^k\times2+2^k\times2+a=2a+2^{k+2}+1 \gcd(a,b)=\gcd(a,1)=1 \operatorname{lcm}(c,d)=\operatorname{lcm}(2^{k+1},2^{k+1}+a)

为了求出 \operatorname{lcm}，我们先计算 \gcd。
由于 k 是 a 的最低位 1，则 a 一定是 2^k 的倍数（因为 a 的后 k-1 位都是 0）。
同理，a-2^k 一定是 2^{k+1} 的倍数，因而 a 一定不是 2^{k+1} 的倍数。
所以，\gcd(2^{k+1},2^{k+1}+a)=\gcd(2\times2^k,2^k(2+m))=2^k，其中 m 为奇数。
所以，\operatorname{lcm}(2^{k+1},2^{k+1}+a)=\frac{2^{k+1}\cdot(2^{k+1}+a)}{\gcd(2^{k+1},2^{k+1}+a)}=\frac{2^{k+1}\cdot(2^{k+1}+a)}{2^k}=2(2^{k+1}+a)=2^{k+2}+2a,

## 补充限制证明 ### 一、检验法 经检验，所有满足题目要求的 $a$ 计算得到的答案均满足题目限制，没有超限。 ### 二、证明 由于 $\left \lfloor \log_210^9 \right \rfloor =29$，所以 $\operatorname{lowbit}(a)_{max}=a=2^{29}=536870912$，$d=a+2*\operatorname{lowbit}(a)_{max}=1610612736\le1634826193$；而接下来 $a$ 最多增长 $463129088$，$2*\operatorname{lowbit}(a)$ 最少减小 $2^{29}\times2-2^{28}\times2=536870912$，即使这两者同时成立，答案也一定减小，但事实上这两者不可能同时成立，答案只会更小，因此当 $a=2^{29}$ 时 $d$ 取最大值，并且 $d$ 是三者中最大的数，从而保证了答案满足题目要求。 --- _经程序检验，$d=1610612736$ 的确是最大答案。_ # 完整代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll t,a; int main() { cin>>t; while(t--) { cin>>a; cout<<1<<' '<<((a&-a)<<1)<<' '<<(a+((a&-a)<<1))<<endl; } return 0; } ```