做 zr 模拟赛的时候有这样一道题目：
给出 \(n\) 个数 \(a_1,a_2,...,a_n\)。求他们的 lcm \(\bmod 998244353\) 的结果。
\(n\le 5000,a_i\le 10^{18}\)。
用 pollard-rho 的人希望你的考场上也能写出来这个东西，那我就没意见了，我先投降。
考虑最朴素的求 \(n\) 个数的 lcm 的过程：假设我们已经算出了 \(x=lcm(a_1,a_2,...,a_i)\)，我们现在想求 \(x\) 和 \(a_{i+1}\) 的 \(\gcd\)，然后把 \(x\) 乘上 \(\frac{a_{i+1}}{\gcd(x,a_{i+1})}\) 就是前 \(i+1\) 个数的 lcm。
难点就是求：\(\gcd(a_{i+1},lcm(a_1,a_2,...,a_i))\)。
第一个想法：这个式子显然可以化成：\(lcm(\gcd(a_{i+1},a_1),\gcd(a_{i+1},a_2),...,\gcd(a_{i+1},a_i))\)。而这 \(i\) 个数里的每一个都是 \(a_{i+1}\) 的约数，所以它们的 lcm 结果还是 \(a_{i+1}\) 的约数，也就是范围是 \(\le 10^{18}\) 的。那我们暴力地把 \(i\) 个 \(\gcd\) 都算出来再求 \(lcm\) 即可。
这样得到一个 \(O(n^2\log V)\) 的做法，显然是无法通过 \(n\le 5000\) 的数据的。
这个做法的问题就是没用充分利用到前面已经算出来的信息。事实上算出 \(\gcd(x,a_{i+1})\) 以后，我们令 \(b_{i+1}=\frac{a_{i+1}}{\gcd(x,a_{i+1})}\)。则 \(\prod_{j=1}^{i}b_j\) 就是 \(a_1,a_2,...,a_i\) 的 lcm。相当于我们把 lcm 这个东西化成了乘积这样简单的形式。那想求 \(\gcd(\prod_{j\le i}b_j,a_{i+1})\) 其实是容易的：因为 \(\gcd(a,b)=\gcd(a\bmod b,b)\)。我们只需要算 \(\prod_{j\le i}b_j\) 对 \(a_{i+1}\) 取模的结果，最后求一次 \(\gcd\) 就可以得到 \(b_{i+1}\)。
此时得到一个 \(O(n^2+n\log V)\) 的做法，就可以通过了。
如果只到这里肯定是不够写一篇的。我们来做这样一个问题：
给出 \(n\) 个数 \(a_1,a_2,...,a_n\)。对每个区间 \([l,r]\) ，求 \(lcm(a_l,a_{l+1},...,a_r)\) 对 \(998244353\) 取模的结果。
数据范围还是 \(n\le 5000,a_i\le 10^{18}\)。
套用上面的做法对每个左端点跑只能做到 \(O(n^3+n^2\log V)\) 的复杂度。我们的核心思路还是找到合适的 \(b_i\) 使得 lcm 能被表示成 \(b_i\) 的乘积的形式。当然你肯定找不到一组 \(b_i\) 满足对于任何的 \([l,r]\) 都有 \(b_l\times ...\times b_r=lcm(b_l,...,b_r)\)，哪有这么好的事情？考虑不断往序列后追加一个元素。然后 \(b_i\) 只需要满足后缀 \(b_i\) 的乘积是后缀的 lcm，拥有这个事情就足够了。
比如说我们添加了一个 \(a_{n+1}=v\) 这样的元素，显然有 \(b_{n+1}=v\)，怎么修改 \(b_1\sim b_n\) 呢。从后往前枚举 \(b_i\)，令 \(g=\gcd(v,b_i)\)，则我们会把 \(b_i\) 和 \(v\) 都是除以 \(g\)，然后接着考虑 \(i-1\)。朴素地做这样一个去更新 \(b_i\)，就得到一个 \(O(n^2\log V)\) 的做法。瓶颈原因还是求 gcd 次数太多。
令 \(c_i\) 是枚举到 \(b_i\) 的时候此时 \(\gcd(b_i,v)\) 的值，也就是说 \(b_i\) 要除以多少。那 \(\prod_{j=i}^{n}c_j\) 其实就是 \(\gcd(\prod_{j=i}^{n}b_j,v)\) 啊。后面这个形式看着就很眼熟。我们算出 \(b_j\) 的后缀积 \(s_j\) 模 \(v\) 的值，这可以 \(O(n)\) 算出。那 \(\prod_{j=i}^{n}c_j\) 就是 \(\gcd(s_j,v)\)。这有什么用呢？因为 \(c\neq 1\) 的位置只有 \(O(\log V)\) 处，如果我们能找到这些位置，就可以把瓶颈处的 \(O(n^2\log V)\) 降下来，不用求那么多次 gcd 了。
而 \(\gcd(s_i,v)\neq gcd(s_{i+1},v)\) 的充要条件是 \(s_{i+1}\bmod \gcd(s_i,v)\neq 0\)。（这是因为 \(s_{i+1}\mid s_i\) 而产生的性质）。说人话就是如果我们知道了 \(\gcd(s_i,v)\) 的值，然后我们已经知道了 \(s_{i+1}\bmod v\) 的值了，那就可以 \(O(1)\) 判断 \(\gcd(s_{i+1},v)\) 是否和 \(\gcd(s_i,v)\) 相等。那就可以 \(O(1)\) 判断 \(c_{i}\) 是否 \(\gt 1\)。那第一步算一下 \(\gcd(s_1,v)\) 就行了啊。
这样我们只用求 \(n\log V\) 次 \(\gcd\)。不过大家应该都知道对一个数重复替换成他和另一个数的 \(\gcd\)，这样一个过程均摊还是 \(O(\log V)\) 的。所以总复杂度就是 \(O(n^2+n\log V)\)。就算实现的菜了一点变成了 \(n\log^2 V\) 也没问题，反正他不是瓶颈。
标签：...,le,gcd,厉害,prod,lcm,log From： https://www.cnblogs.com/Cry-For-theMoon/p/18426320