CF2275F.Tea Blend
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Recently, K1o0n made an impulsive purchase of n 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 ai.
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 j packs in order into the teapot, and then adds one more spoon from the pack with number i. We denote the resulting blend by (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)
K1o0n pours the finished teapot into identical cups: he can pour it into d cups if and only if d — is a natural divisor of the number F(i,j), and each cup gets the same amount. He calls a blend capricious if the number of suitable d is odd.
Count how many capricious blends K1o0n can brew, that is, how many pairs (i,j) with 1≤i≤n and 1≤j≤n give an odd number of natural divisors of the number F(i,j).
最近,K1o0n 冲动地购买了 n 包茶叶,现在正琢磨着何时才能尝遍所有茶饮组合。他对茶很挑剔,因此立刻为每包茶赋予了一个“浓强度”——一个整数 ai。
这些茶包按购买顺序摆放在架子上,而 K1o0n 又懒得重新整理:他在泡茶时,会依次将前 j 包茶全部倒入茶壶中,再额外加入第 i 包茶的一勺。我们将由此得到的茶饮组合记作 (i,j),并将其“浓强度”定义为所有入壶成分浓强度的乘积:
F(i,j)=ai⋅∏k=1jak=ai⋅(a1⋅a2⋅…⋅aj)
K1o0n 将泡好的茶均匀分装进若干个相同的茶杯中:当且仅当 d 是 F(i,j) 的一个正整数约数时,他才能恰好分装进 d 杯,且每杯茶量相等。若某个茶饮组合 (i,j) 对应的 F(i,j) 恰好有奇数个正整数约数,则 K1o0n 称该组合为“任性的”。
请计算 K1o0n 能够冲泡出多少种“任性的”茶饮组合,即满足 1≤i≤n 且 1≤j≤n 的数对 (i,j) 中,使得 F(i,j) 的正整数约数个数为奇数的个数。
输入格式
The first line contains an integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains an integer n (1≤n≤2⋅105) — the number of tea packs.
The second line of each testcase contains n integers a1,a2,…,an (1≤ai≤106) — the strengths of the teas.
It is guaranteed that the sum of n over all testcases does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤104)—— 测试用例的数量。
每个测试用例的第一行包含一个整数 n(1≤n≤2⋅105)—— 茶包的数量。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an(1≤ai≤106)—— 各种茶的浓度。
保证所有测试用例的 n 值之和不超过 2⋅105。
输出格式
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测评打分。不知道怎么写?