出题人：一只书虫仔 Data&验题人：w33z

Description

给定两个长为 $n$ 的序列 $a_i,b_i$，定义一个区间 $[l,r]$ 是相克的当且仅当：

$$\gcd(a_l,a_{l+1},\cdots,a_r)=\text{lcm}(b_l,b_{l+1},\cdots,b_r) $$

求：

• 最长的相克区间长度。
• 相克区间的数量。

$1 \le n \le 10^5$，$1 \le a_i,b_i \le 1000$。

Solution

Subtask 1：我会暴力！暴力解决问题。

Subtask 2：我会 ST 表！暴力枚举所有区间，预处理区间 $\gcd\ \text{lcm}$。

正解：正解是根据 $30$ 分的进一步暴力解法优化而来的。让我们先固定区间的左端点 $l$，然后往右去寻找右端点。我们都知道，区间越大，$\gcd$ 只会不变或者越来越小，$\text{lcm}$ 只会不变或者越来越大，因此如果右端点越靠近 $l$，那么 $\gcd$ 就会越大 $\text{lcm}$ 就会越小，反之亦然，也就是说，我们可以通过上面这个过程去二分在 $[l,n]$ 中最大满足要求的区间 $[l',r']$ 的左端点和右端点，然后每一个子区间肯定都满足要求，因此第二问答案加上 $r'-l'+1$ 即可，第一问答案与 $r'-l'+1$ 取个 $\max$。

然后预处理区间 $\gcd\ \text{lcm}$ 依然是 ST 表。

令 $M$ 为值域，预处理 $\mathcal O(n \log n\log M)$，枚举左端点 + 二分 $\mathcal O(n \log n\log M)$。

评价：思维代码均比较简单的简单题，给良心的出题人点赞！