P15019 [UOI 2020 II Stage] 倍乘

哥萨克胡子在研究一种非常有趣的操作：将一个数乘以它的任意除数。例如，他可以将数字 $6$ 乘以 $1$、$2$、$3$ 或 $6$，分别得到 $6$、$12$、$18$ 或 $36$。 接着，他学会了将这种操作应用于由 $n$ 个数组成的数组 $a$ 上。为此，他只需将数组中的每个数 $a_i$ 乘以 $a_i$ 的任意除数。他将这个发明出来的操作称为 **“数组倍乘”**。 之后，胡子立刻决定将数对 $(l, r)$ 称为 **“优美数对”**，如果满足以下条件： - $1 \leq l \leq r \leq n$。 - 可以通过不超过 $k$ 次 **“数组倍乘”** 操作，使得所有数 $a_l, a_{l+1}, \dots, a_r$ 变得相同。 你的任务是：对于给定的数组，找出 **“优美数对”** 的数量。哥萨克最近发现，数组中所有数的 **质因数** 都小于 $30$。提醒一下，**质数** 是指恰好有两个不同正因数的自然数。

第一行包含三个整数 $n$、$k$ 和 $g$ ($1 \leq n \leq 2 \cdot 10^5$, $0 \leq k \leq 100$, $0 \leq g \leq 12$) —— 分别表示数组的元素个数、**“数组倍乘”** 操作的最大允许次数，以及测试点所属的区块编号。 第二行包含 $n$ 个整数 $a_1, a_2,..., a_n$ ($1 \leq a_i \leq 10^6$) —— 数组 $a$ 的元素。保证没有任何一个数能被大于 $30$ 的质数整除。

输出一个数字 —— **“优美数对”** 的数量。

第一个样例的解释： 考虑所有 **“优美数对”**： 数对 $(1, 1)$、$(2, 2)$、$(3, 3)$、$(4, 4)$ 和 $(5, 5)$ 即使不进行 **“数组倍乘”** 也是优美的。 - $(1, 2)$：将 $a_1$ 乘以 $3$，$a_2$ 乘以 $1$。 - $(1, 3)$：将 $a_1$ 乘以 $6$，$a_2$ 乘以 $2$，$a_3$ 乘以 $3$。 - $(2, 3)$：将 $a_2$ 乘以 $2$，$a_3$ 乘以 $3$。 - $(3, 4)$：将 $a_3$ 乘以 $4$，$a_4$ 乘以 $2$。 ### 评分细则 - （6 分） $n \leq 10^3, k = 0$。 - （6 分） $n \leq 2 \cdot 10^5, k = 0$。 - （8 分） $n \leq 10^2, k = 100$。 - （6 分） $n \leq 10^3, k = 100$。 - （6 分） $n \leq 2 \cdot 10^5, k = 100$。 - （8 分） $n \leq 10^3$，所有 $a_i = 2^{m_i}$，其中 $m_i$ 为非负整数。 - （7 分） $n \leq 2 \cdot 10^5$，所有 $a_i = 2^{m_i}$，其中 $m_i$ 为非负整数。 - （5 分） $n \leq 10^3$，所有 $a_i = 2^{m_i} \cdot 3^{l_i}$，其中 $m_i$ 和 $l_i$ 为非负整数。 - （10 分） $n \leq 2 \cdot 10^5$，所有 $a_i = 2^{m_i} \cdot 3^{l_i}$，其中 $m_i$ 和 $l_i$ 为非负整数。 - （10 分） $n \leq 10^2$。 - （11 分） $n \leq 10^3$。 - （17 分） $n \leq 2 \cdot 10^5$。 翻译由 DeepSeek V3 完成