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

做这道题需要用到的：[The On-Line Encyclopedia of Integer Sequences, OEIS](https://oeis.org/)。

---

首先 $7$ 分暴力是极易的。

```cpp
cin >> a;

bool flg = false;
for (int b = 1; b <= 100 && !flg; ++ b )
	for (int c = 1; c <= 100 && !flg; ++ c )
		for (int d = 1; d <= 100 && !flg; ++ d ) {
			if (a + b + c + d == __gcd(a, b) + c * d / __gcd(c, d)) {
				flg = true;
				cout << /*a << ' ' <<*/ b << ' ' << c << ' ' << d << '\n';
				break;
			}
		}
```

你打一下表，输出所有 $a \in [1, 50]$ 的答案。（为了美观放[云剪贴板](https://www.luogu.com.cn/paste/4mvukftj)里了，你可以分屏看。）

然后就是 OEIS 了。我们约定 $\operatorname{lowbit}x = $`x & -x`。

第二列 $b = 1$。这显然。

第三列 $c$ 是 [A171977](https://oeis.org/A171977)。OEIS 告诉我们：

> $c(a) = 2^{k+1}$ where $2^k$ is the highest power of $2$ dividing $a$.
> 
> 即 $c(a) = 2^{k + 1}$，其中 $2^k \mid a$ 且 $k$ 最大。

你发现 $2^k$ 实际上就是 $\operatorname{lowbit} a$。所以 $c(a) = \operatorname{lowbit} a\times 2$。

第四列 $d$ 是 [A349102](https://oeis.org/A349102)。OEIS 告诉我们：

> Increase the odd part of $a$ to the next greater odd number to get $d(a)$.
>
> 即设 $a = b \times 2^k$，其中 $b$ 是奇数（或者说 $k$ 最大）。将 $b$ 增加到较大的下一个奇数 $b'$。那么 $d(a) = b' \times 2^k$。

显然 $b' = b + 2$，即 $d(a) = (b + 2) \times 2^k$。其中 $2^k$ 还是 $\operatorname{lowbit} a$。即 $d(a) = \left(\dfrac{a}{\operatorname{lowbit} a} + 2\right) \times \operatorname{lowbit} a$。

所以：

$$
\left\{
\begin{matrix}
b = 1 \\
c = \operatorname{lowbit} a\times 2 \\
d = \left(\dfrac{a}{\operatorname{lowbit} a} + 2\right) \times \operatorname{lowbit} a
\end{matrix}
\right.
$$

单词询问 $\mathcal O(1)$。

```cpp
#include <bits/stdc++.h>

using namespace std;

signed main() {
	int T;
	cin >> T;
	while (T -- ) {
		int a;
		cin >> a;
		cout << 1 << ' ' << (a & -a) * 2 << ' ' <<  (a & -a) * (a / (a & -a) + 2) << '\n';
	}
	return 0;
}
```

正在渲染内容...