1422F
【拆贡献】CF1422F Boring Queries
考虑质因数分解,我们求区间的 $lcm$ 就是 $\prod a_i$ 除以一些东西。 不难发现如果算 $x^k \in lcm$ 那么我们只能算一次,那么我们直接把这个东西挂在前一个出现的位置即可。 使用主席树维护即可。这个题,很难。 ```cpp // LUOGU_RID: 123092767 ......
CF1422F Boring Queries
# CF1422F Boring Queries ## 题意 询问区间 $lcm$,强制在线。 ## 题解 首先考虑每个质因子对于答案的贡献。 对于一个质因子 $p_i$ 来说其对于区间 $[l,r]$ 的贡献是其最高次幂。 首先考虑离线做法,扫描线,线段树维护答案。 将当前加入的数 $a_i$ 分 ......