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

分析

首先可以看出奇数的情况很好解决，于是先考虑 $a$ 是奇数的情况，比赛时时间紧张我一开始就是考虑令 $b=a,c=3$ 的情况，此时可以看出令 $d=a÷2+2$，可以满足条件，但如过这样，$a$ 是 $3$ 的倍数时，构造就不合理了，因为时间问题，比赛时想都没想就加了个特判，如果 $a$ 是 $3$ 的倍数，$b=a,c=2,d=a+2$，这样就可以了，但后来一想，实际上所有奇数都可以这么做，进一步思考，$b=a$ 和 $b=1$ 的效果其实一样，由此我们得到了对于 $a$ 为奇数时的构造方法，$b=1,c=2,d=a+2$。

比赛还剩三十分钟，赶紧开始想偶数的构造，我当时想到的方法是令 $b=a+p,c=4,d=2a+p+3$，这个方案的意思是使 $b$ 等于一个与 $a$ 互质的数，为了达到这个目的，我选择了令 $p=5\times 10^8+3$，这样只要使 $\mathrm{lcm}(c,d)=2a+p-1$ 即可，但是会发现 $2a+p+3>1634826193$，直到比赛结束我也没想到正解，赛后突然发现如果 $a+b+c+d=\gcd (a,b)+\mathrm{lcm}(c,d)$，那么 $ap+bp+cp+dp=\gcd (ap,bp)+\mathrm{lcm}(cp,dp)$，我们令 $a÷p$ 为一个奇数，不就可以将偶数转化为奇数了吗，稍加思考，使 $a$ 保持不变，将 $p$ 再乘回去，$b=1\times p=p,c=2\times p=2p$，那么 $d$ 就需要等于 $a+2p$，问题来了，$p$ 等于多少合适呢，其他数都不行，只能是 $-a\&a$，是这个数实际上就是能被 $a$ 整除的最大的 $2^k$ 中的 $k$。

于是就有了对于偶数的构造方案：

令 $k=-a\&a$，$b=k,c=2k,d=a+2k$。

事实上再看一下这个方案，它对于奇数仍然适用，于是便有了这道题的正解。

代码

#include<bits/stdc++.h>
using namespace std;
long long t,a,temp;
int main()
{
   
  cin>>t;
  while(t--)
  {
   
    cin>>a;
    temp=a&-a;
    cout<<temp<<" "<<temp*2<<" "<<temp*2+a;
    cout<<endl;
  }
  return 0;
}