CF2275F.Tea Blend

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Recently, K1o0n made an impulsive purchase of nn packs of tea and is now wondering when he will manage to try all the blends. He is picky about tea, so he immediately assigned each pack a strength — an integer aia_i.

The packs are arranged on the shelf in the order they were bought, and K1o0n is too lazy to sort them out: when brewing tea, he pours the first jj packs in order into the teapot, and then adds one more spoon from the pack with number ii. We denote the resulting blend by (i,j)(i, j), and define its strength as the product of the strengths of everything that went into it:

F(i,j)=ai⋅∏k=1jak=ai⋅(a1⋅a2⋅…⋅aj)F(i, j) = a_i \cdot \prod_{k=1}^{j} a_k = a_i \cdot \left(a_1 \cdot a_2 \cdot \ldots \cdot a_j\right)

K1o0n pours the finished teapot into identical cups: he can pour it into dd cups if and only if dd — is a natural divisor of the number F(i,j)F(i, j), and each cup gets the same amount. He calls a blend capricious if the number of suitable dd is odd.

Count how many capricious blends K1o0n can brew, that is, how many pairs (i,j)(i, j) with 1≤i≤n1 \le i \le n and 1≤j≤n1 \le j \le n give an odd number of natural divisors of the number F(i,j)F(i, j).

最近,K1o0n 冲动地购买了 nn 包茶叶,现在正琢磨着何时才能尝遍所有茶饮组合。他对茶很挑剔,因此立刻为每包茶赋予了一个“浓强度”——一个整数 aia_i。

这些茶包按购买顺序摆放在架子上,而 K1o0n 又懒得重新整理:他在泡茶时,会依次将前 jj 包茶全部倒入茶壶中,再额外加入第 ii 包茶的一勺。我们将由此得到的茶饮组合记作 (i,j)(i, j),并将其“浓强度”定义为所有入壶成分浓强度的乘积:

F(i,j)=ai⋅∏k=1jak=ai⋅(a1⋅a2⋅…⋅aj)F(i, j) = a_i \cdot \prod_{k=1}^{j} a_k = a_i \cdot \left(a_1 \cdot a_2 \cdot \ldots \cdot a_j\right)

K1o0n 将泡好的茶均匀分装进若干个相同的茶杯中:当且仅当 dd 是 F(i,j)F(i, j) 的一个正整数约数时,他才能恰好分装进 dd 杯,且每杯茶量相等。若某个茶饮组合 (i,j)(i, j) 对应的 F(i,j)F(i, j) 恰好有奇数个正整数约数,则 K1o0n 称该组合为“任性的”。

请计算 K1o0n 能够冲泡出多少种“任性的”茶饮组合,即满足 1≤i≤n1 \le i \le n 且 1≤j≤n1 \le j \le n 的数对 (i,j)(i, j) 中,使得 F(i,j)F(i, j) 的正整数约数个数为奇数的个数。

输入格式

The first line contains an integer tt (1≤t≤1041 \le t \le 10^4) — the number of testcases.

The first line of each testcase contains an integer nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) — the number of tea packs.

The second line of each testcase contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤1061 \le a_i \le 10^6) — the strengths of the teas.

It is guaranteed that the sum of nn over all testcases does not exceed 2⋅1052 \cdot 10^5.

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)—— 测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)—— 茶包的数量。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤1061 \le a_i \le 10^6)—— 各种茶的浓度。

保证所有测试用例的 nn 值之和不超过 2⋅1052 \cdot 10^5。

输出格式

For each testcase, output one integer — the number of capricious blends.

Note that the answer may not fit into a 32-bit type. Use a 64-bit type (long long in C++, long in Java).

对于每个测试用例,输出一个整数——即任性的混合物的数量。

注意:答案可能无法用 32 位类型表示。请使用 64 位类型(C++ 中为 long long,Java 中为 long)。

输入输出样例

  • 输入#1

    4
    4
    2 3 6 4
    4
    974153 980051 988027 1
    8
    12 3 5 45 1 7 63 2
    1
    13

    输出#1

    4
    4
    11
    1

说明/提示

null

输入解题思路,AI测评打分。不知道怎么写?

首页