让你求区间lcm，\(n\le 50000,A_i\le 10^9\)。
感觉很简单啊。平衡规划 + 质因数分解 + RMQ + 莫队 + 桶 没了啊。
具体就是 小的质因子我们 RMQ求个最大值。
大的质因子我们 莫队 + 桶 维护一下。
时间复杂度有点卡，不过2s就很稳了。
莫队 + 树状数组就没了啊。
手速题。要求20Min内1A。
5956. 【NOIP2018模拟11.7A组】easy LCA
降智题。不知道为什么没有想出来。
一个结论：序列的LCA是两两LCA的min，然后求出相邻LCA后随便做就好了。
5663. 【GDOI2018Day1模拟4.17】呼吸决定
直接上杜教筛就好了。
如果让\(f(i)=\mu(i)i^m,g(i)=i^m\)，可以得到\(f·g=h=[n=1]\)，然后会发现变成一个\[f(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^nf(d)S(\frac{n}{d})\]
然后这个\(S(i)\)就是自然数幂和，套一个拉格朗日插值就好了。
原文：https://www.cnblogs.com/Pro-king/p/10688827.html