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

hh弟中弟 · 2024-09-10 14:21:06 · 题解

设 \gcd(c,d)=x,c=qx,d=ex\ [\gcd(q,e)=1]，则 a+b-\gcd(a,b)=(qe-q-e)x。\ 考虑右边 qe-q-e 的取值，当 q=2,2\nmid e 时，它可以表示任意奇数。

• 当 a 为奇数时，可以取 b=1，这样左边为 a，取 q=2,e=a+2,x=1，右边为 a，等式成立，此时 b=1,c=2,d=a+2，在合法范围中。
• 当 a 为偶数时，考虑将 a 转化为奇数，设 a=2^kw，取 x=2^k，此时就转化为了 a 为奇数的情况，取 b=1,q=2,e=w+2,x=2^k，等式成立，此时 b=1,c=2\times 2^k,d=(w+2)\times 2^k，因为 2^k\le536870912，所以取值在合法范围中。

综上 b=1,c=2\times\operatorname{lowbit}(a),d=a+2\times\operatorname{lowbit}(a) 时，等式成立。