CF1609C Complex Market Analysis

在进行复杂的市场分析时，William 遇到了如下问题： 给定一个长度为 $n$ 的数组 $a$ 和一个自然数 $e$，请计算满足以下条件的自然数对 $(i, k)$ 的数量： - $1 \leq i, k$ - $i + e \cdot k \leq n$ - 积 $a_i \cdot a_{i + e} \cdot a_{i + 2e} \cdot \ldots \cdot a_{i + ke}$ 是一个质数。 质数（或称素数）是指大于 $1$ 且不能被两个更小的自然数相乘得到的自然数。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \leq t \leq 10\,000$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $e$（$1 \leq e \leq n \leq 2 \times 10^5$），分别表示数组的长度和数字 $e$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$），表示数组的内容。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一行，表示满足条件的数对 $(i, k)$ 的数量。

在第一个样例测试点中，有两个数对满足条件： 1. $i = 2, k = 1$，此时积为：$a_{2} \cdot a_{5} = 2$，是一个质数。 2. $i = 3, k = 1$，此时积为：$a_{3} \cdot a_{6} = 19$，是一个质数。 在第二个样例测试点中，没有满足条件的数对。 在第三个样例测试点中，有四个数对满足条件： 1. $i = 1, k = 1$，此时积为：$a_{1} \cdot a_{4} = 2$，是一个质数。 2. $i = 1, k = 2$，此时积为：$a_{1} \cdot a_{4} \cdot a_{7} = 2$，是一个质数。 3. $i = 3, k = 1$，此时积为：$a_{3} \cdot a_{6} = 2$，是一个质数。 4. $i = 6, k = 1$，此时积为：$a_{6} \cdot a_{9} = 2$，是一个质数。 在第四个样例测试点中，没有满足条件的数对。 在第五个样例测试点中，有五个数对满足条件： 1. $i = 1, k = 1$，此时积为：$a_{1} \cdot a_{2} = 2$，是一个质数。 2. $i = 1, k = 2$，此时积为：$a_{1} \cdot a_{2} \cdot a_{3} = 2$，是一个质数。 3. $i = 1, k = 3$，此时积为：$a_{1} \cdot a_{2} \cdot a_{3} \cdot a_{4} = 2$，是一个质数。 4. $i = 2, k = 1$，此时积为：$a_{2} \cdot a_{3} = 2$，是一个质数。 5. $i = 2, k = 2$，此时积为：$a_{2} \cdot a_{3} \cdot a_{4} = 2$，是一个质数。 在第六个样例测试点中，没有满足条件的数对。 由 ChatGPT 4.1 翻译