#P14926. [uoi2020-2s]哥萨克·乌斯与补乘

[uoi2020-2s]哥萨克·乌斯与补乘

题目描述

哥萨克·乌斯研究了一种很有趣的操作:把一个数乘以它的任意一个约数。例如,对于数字 66,他可以把它乘以 11、22、33 或 66,分别得到 66、1212、1818 或 3636。

接着,他学会了把这种操作用于一个由 nn 个数组成的数组 aa。执行一次操作时,他会把数组中每个数 aia_i 都乘以 aia_i 的任意一个约数。乌斯把这个操作命名为“数组补乘”。

随后,乌斯称一对数 (l,r)(l,r) 是“好的”,如果满足以下条件:

  • 1≤l≤r≤n1\le l\le r\le n;
  • 可以执行不超过 kk 次“数组补乘”,使得 al,al+1,…,ara_l,a_{l+1},\ldots,a_r 全部变得相等。

你的任务是:给定数组,求“好的”数对数量。

最近哥萨克发现,数组中所有数的质因子都小于 3030。回忆一下,质数是恰好有两个不同正约数的自然数。

输入格式

第一行包含三个整数 n,k,gn,k,g(1≤n≤2⋅1051\le n\le 2\cdot 10^5,0≤k≤1000\le k\le 100,0≤g≤120\le g\le 12),分别表示数组元素个数、最多允许执行的“数组补乘”次数以及测试所属的评分块编号。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤1061\le a_i\le 10^6),表示数组 aa 的元素。保证不存在一个数能被大于 3030 的质数整除。

输出格式

输出一个整数,表示“好的”数对数量。

输入

5 1 0
6 18 12 24 54

输出

9

数据范围与评分

  1. (66 分)n≤103,k=0n\le 10^3, k=0。
  2. (66 分)n≤2⋅105,k=0n\le 2\cdot 10^5, k=0。
  3. (88 分)n≤102,k=100n\le 10^2, k=100。
  4. (66 分)n≤103,k=100n\le 10^3, k=100。
  5. (66 分)n≤2⋅105,k=100n\le 2\cdot 10^5, k=100。
  6. (88 分)n≤103n\le 10^3,所有 ai=2mia_i=2^{m_i},其中 mim_i 为非负整数。
  7. (77 分)n≤2⋅105n\le 2\cdot 10^5,所有 ai=2mia_i=2^{m_i},其中 mim_i 为非负整数。
  8. (55 分)n≤103n\le 10^3,所有 ai=2mi⋅3lia_i=2^{m_i}\cdot 3^{l_i},其中 mi,lim_i,l_i 为非负整数。
  9. (1010 分)n≤2⋅105n\le 2\cdot 10^5,所有 ai=2mi⋅3lia_i=2^{m_i}\cdot 3^{l_i},其中 mi,lim_i,l_i 为非负整数。
  10. (1010 分)n≤102n\le 10^2。
  11. (1111 分)n≤103n\le 10^3。
  12. (1717 分)n≤2⋅105n\le 2\cdot 10^5。