昨晚 VP 的时候想了半个多小时的怎么卡质因数分解的常。
给定两个长度为 \(n\) 的序列 \(a\) 与 \(b\)，对每一个 \(i\) 固定一个 \(d_i\)，使得 \(d_i \mid a_i\)。将 \(b_i \times d_i\) 记为一个新的序列 \(c\)，你要使得 \(c\) 的连续段最少。
\(n \le 10^5\)，\(a_i \le 10^9\)，\(b_i \le 2 \times 10^4\)。
我们考虑一个贪心：每次都尽量向后走，直到走到无法满足题目要求的 \(i\) 为止，再 \(ans \gets ans + 1\)，另起一段，直到走完整个序列。容易证明贪心的正确性，现在需要考虑的就是如何验证是否存在满足条件的 \(c_i\)。
对于合法的一段 \([l, r]\)，我们设其对应的 \(c_i\) 为 \(c\)，合法的要求是对于每一个 \(i \in [l, r]\)，都有 \(d_i \mid a_i\)，也就是 \(c_i \mid a_i \times b_i\)，那么显然，如果 \(\gcd_{l \le i \le r} a_i \times b_i\) 是 \(c\) 的倍数的话，\([l, r]\) 这一段才合法。显然有对于任意的 \(i \in [l, r]\)，都有 \(b_i \mid c\)。那么我们容易看出最小的，也是最优的 \(c\) 为 \(\operatorname{lcm}_{l \le i \le r} b_i\)。那么 \([l, r]\) 这一段合法等价于 \(\operatorname{lcm}_{l \le i \le r} b_i | \gcd_{l \le i \le r} a_i \times b_i\)，贪心即可做到 \(\mathcal{O}(n \log |S|)\)，其中 \(|S|\) 为值域大小。
标签：10,le,mid,Candy,times,合法,CF1798C,Store,贪心 From： https://www.cnblogs.com/forgot-dream/p/17638176.html