P17759 「RSOI-3H」数组划分 / partition

题目来源：【HT-126-Div.2】核桃 CSP-S 组模拟赛

给定一个长度为 $n$ 的正整数数组 $A$。 你需要将数组 $A$ 划分为若干个连续的非空子段，且必须满足：对于划分出的每一个子段，其内部最大值与最小值的最大公约数严格大于 $1$。 另有 $k$ 组约束，每组约束由两个整数 $(u, v)$ 组成，表示原数组中下标为 $u$ 和下标为 $v$ 的元素**不能**被划分在同一个连续子段内。 求所有合法的划分方案数，答案对 $998244353$ 取模。

第一行包含两个非负整数 $n, k$。 第二行包含 $n$ 个正整数，表示数组 $A_1, A_2, \dots, A_n$。 接下来 $k$ 行，每行包含两个整数 $u, v$，表示一组不能在同一子段的下标约束。

输出一行一个整数，表示合法的划分方案数对 $998244353$ 取模后的结果。

**【样例解释 #1】** 本样例无约束条件，所有合法的划分方案如下： * `[2], [4], [3], [6]`：各子段 $\gcd$ 分别为 2, 4, 3, 6，均合法。 * `[2, 4], [3], [6]`：`[2, 4]` 最大值为 4，最小值为 2，$\gcd(4, 2) = 2 > 1$，合法。 * `[2], [4], [3, 6]`：`[3, 6]` 最大值为 6，最小值为 3，$\gcd(6, 3) = 3 > 1$，合法。 * `[2, 4], [3, 6]`：合法。 * `[2], [4, 3, 6]`：`[4, 3, 6]` 最大值为 6，最小值为 3，$\gcd(6, 3) = 3 > 1$，合法。 * `[2, 4, 3], [6]`：`[2, 4, 3]` 最大值为 4，最小值为 2，$\gcd(4, 2) = 2 > 1$，合法。 * `[2, 4, 3, 6]`：整个数组最大值为 6，最小值为 2，$\gcd(6, 2) = 2 > 1$，合法。 注意，`[2], [4, 3], [6]` 是非法的，因为 `[4, 3]` 的 $\gcd(4, 3) = 1$。共计 7 种合法方案。 **【数据范围】** **本题采用捆绑测试。** 对于 $100\%$ 的数据，满足 $1 \le n,A_i \le 2\times 10^5$，$0 \le k \le 2\times 10^5$，$1 \le u < v \le n$。 | Subtask | $n\le$ | $k\le$ | 特殊性质 | 分值 | | :----: | :----: | :----: | :----: | :----: | | 1 | $500$ | $500$ | 无 | $10$ | | 2 | $5000$ | $5000$ | ^ | $15$ | | 3 | $8\times 10^4$ | $8\times 10^4$ | ^ | $10$ | | 4 | $2\times 10^5$ | $2\times 10^5$ | 所有的 $A_i$ 均相等 | $10$ | | 5 | ^ | ^ | 所有的 $A_i$ 均为质数 |$10$ | | 6 | ^ | $0$ | 无 |$15$ | | 7 | ^ | $2\times 10^5$ | ^ | $30$ |