CF2275F Tea Blend

最近，K1o0n 冲动地买下了 $n$ 包茶叶，现在他想知道自己什么时候才能把所有口味都尝一遍。他对茶很挑剔，于是立刻给每包茶叶都分配了一个强度——一个整数 $a_i$。 茶包按照购买顺序依次放在架子上，而 K1o0n 太懒了，不想整理它们：每次泡茶时，他会先将前 $j$ 包按顺序全部倒入茶壶，然后再从第 $i$ 包茶里多加一勺。我们用 $(i, j)$ 表示这种混合方式，并定义其强度为投入所有原料的强度的乘积： $$ F(i, j) = a_i \cdot \prod_{k=1}^{j} a_k = a_i \cdot (a_1 \cdot a_2 \cdot \ldots \cdot a_j) $$ K1o0n 会把泡出来的茶均分到若干个完全相同的杯子里：只有当 $d$ 是 $F(i, j)$ 的正约数时，他才能分到 $d$ 个杯子中，并且每个杯子里的量完全相同。他将“可分配杯数 $d$ 的个数为奇数”的混合称为“任性”的。 请你计算 K1o0n 能泡出多少种任性的混合，也就是说，有多少组 $(i, j)$（$1 \le i \le n$，$1 \le j \le n$）能使得 $F(i, j)$ 的正约数个数为奇数。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示茶包的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$），表示每包茶的强度。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示任性混合的数量。 注意，答案可能超出 32 位整数范围，请使用 64 位整数类型（C++ 中用 long long，Java 中用 long）。

由 ChatGPT 5 翻译