题目描述

哥萨克胡子在研究一种非常有趣的操作：将一个数乘以它的任意除数。例如，他可以将数字 $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$ 的质数整除。

输出格式

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

5 1 0
6 18 12 24 54

9

10 1 0
5 15 225 135 1 4 8 8 1024 64

16

提示

第一个样例的解释：

考虑所有 “优美数对”：

数对 $(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 完成