红石钟：题解¶
解法比较¶
查表 GCD 与欧几里得 GCD 是并列方案：询问很多且可存储值域表时可用前者；标程采用后者，额外空间为常数。
出题人解法同样由最大公约数计算最小公倍数，但先对整个数值范围做线性筛，将每个数拆成至多三个适合查询的因子。小因子不超过 \(\sqrt U\) ，大因子为可直接测试整除的素数；小因子之间的 GCD 预先放入二维表。查询时逐个求因子与剩余另一数的 GCD 并除去已匹配部分，其乘积就是完整 GCD，避免重复计入素因子。因子个数有常数界，预处理为 \(O(U)\) 时间、\(O(U)\) 空间，之后总查询时间为 \(O(n)\) ，按固定字长运算计。
Codex（GPT-6）采用的实现按题面公式依次生成询问，用欧几里得算法直接求 GCD，时间为 \(O(n\log U)\) ，额外空间为 \(O(1)\) .收益是取消整个值域的表和预处理，实现更短；代价是每次查询增加对数上界。若询问极多且值域表可以承受，查表方案仍有价值，可按询问规模与可用内存选择。
最小公倍数¶
两个周期同时结束的正时刻必须同时为两个周期的倍数。最早的时刻就是最小公倍数：
用最大公约数计算每次询问的答案，分别异或进两个累积变量。每次询问之后立即按对应公式更新 \(a\) ，不能把两次更新合并或提前执行。
正确性¶
最小公倍数正好是两时钟第一次同时结束周期的正时刻。循环在第 \(i\) 轮先处理第 \(2i-1\) 次询问，再更新参数、处理第 \(2i\) 次询问并再次更新，与题目生成过程逐步一致。因此两个累积变量分别包含所有奇数次和偶数次询问的答案。
复杂度与实现¶
用 \(U\) 表示周期和初始参数的数值上界，本题 \(U=10^7\) .每次最大公约数计算需 \(O(\log U)\) 时间，总时间为 \(O(n\log U)\) ，额外空间为 \(O(1)\) ，按固定字长整数运算计。
最小公倍数和 \(a^2\) 可能超过 32 位整数范围，使用 64 位整数。先除以最大公约数，再乘以 \(a\) ；所有询问在线生成，无需保存。