# 红石钟：题解

## 解法比较

查表 GCD 与欧几里得 GCD 是并列方案：询问很多且可存储值域表时可用前者；标程采用后者，额外空间为常数。

出题人解法同样由最大公约数计算最小公倍数，但先对整个数值范围做线性筛，将每个数拆成至多三个适合查询的因子。小因子不超过 $\sqrt U$ ，大因子为可直接测试整除的素数；小因子之间的 GCD 预先放入二维表。查询时逐个求因子与剩余另一数的 GCD 并除去已匹配部分，其乘积就是完整 GCD，避免重复计入素因子。因子个数有常数界，预处理为 $O(U)$ 时间、$O(U)$ 空间，之后总查询时间为 $O(n)$ ，按固定字长运算计。

Codex（GPT-6）采用的实现按题面公式依次生成询问，用欧几里得算法直接求 GCD，时间为 $O(n\log U)$ ，额外空间为 $O(1)$ .收益是取消整个值域的表和预处理，实现更短；代价是每次查询增加对数上界。若询问极多且值域表可以承受，查表方案仍有价值，可按询问规模与可用内存选择。

## 最小公倍数

两个周期同时结束的正时刻必须同时为两个周期的倍数。最早的时刻就是最小公倍数：

$$\operatorname{lcm}(i,a)=\frac{i}{\gcd(i,a)}\,a$$

用最大公约数计算每次询问的答案，分别异或进两个累积变量。每次询问之后立即按对应公式更新 $a$ ，不能把两次更新合并或提前执行。

## 正确性

最小公倍数正好是两时钟第一次同时结束周期的正时刻。循环在第 $i$ 轮先处理第 $2i-1$ 次询问，再更新参数、处理第 $2i$ 次询问并再次更新，与题目生成过程逐步一致。因此两个累积变量分别包含所有奇数次和偶数次询问的答案。

## 复杂度与实现

用 $U$ 表示周期和初始参数的数值上界，本题 $U=10^7$ .每次最大公约数计算需 $O(\log U)$ 时间，总时间为 $O(n\log U)$ ，额外空间为 $O(1)$ ，按固定字长整数运算计。

最小公倍数和 $a^2$ 可能超过 32 位整数范围，使用 64 位整数。先除以最大公约数，再乘以 $a$ ；所有询问在线生成，无需保存。