gcd 与 lcm 题解

思路

若存在合法序列，则必有 $x\mid y$。把序列中每个数都除以 $x$，问题变成统计最大公约数为 $1$、最小公倍数为 $r=y/x$ 的序列。

设质数 $p$ 在 $r$ 中的指数为 $d$。序列中每个数在质因子 $p$ 上的指数只能取 $0,1,\ldots,d$。为了让整体最大公约数在这一维上的指数为 $0$，至少一个位置必须取 $0$；为了让整体最小公倍数在这一维上的指数为 $d$，至少一个位置必须取 $d$。

不同质因子的指数选择互相独立，因此分别计数后相乘即可。

做法

固定一个指数差 $d$。不加限制时共有 $(d+1)^n$ 种取法。缺少指数 $0$ 的取法有 $d^n$ 种，缺少指数 $d$ 的取法也有 $d^n$ 种，同时缺少两端的取法有 $(d-1)^n$ 种。由容斥原理，合法取法数为

枚举并分解 $r$ 的全部质因数，对每个指数差计算上述值并乘入答案。幂使用二进制快速幂计算。

第一个子任务还可以对每个质因子维护四种状态：是否已经出现指数 $0$、是否已经出现指数 $d$，逐位置转移，复杂度与 $n$ 成正比。第二个子任务可以直接循环相乘计算三次幂。满分做法把幂运算优化为二进制快速幂。

上述乘法成立，是因为一个正整数的所有质因数指数唯一确定；逐个质因子独立选择指数后，恰好对应唯一的序列，且每个质因子的两端都出现当且仅当整体最大公约数和最小公倍数分别达到要求。

复杂度

对每组询问，试除分解 $r=y/x$ 需要 $O(\sqrt r)$ 次整除判断，每个质因子的计数需要 $O(\log n)$ 次模乘。总时间复杂度为 $O(Q\sqrt r+Q\omega(r)\log n)$，其中 $\omega(r)$ 是不同质因数个数；额外空间复杂度为 $O(1)$。