#A. 平方数(sqrt)

    Type: Default File IO: sqrt 1000ms 256MiB

平方数(sqrt)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡有超级大的正整数 NN。他用以下这种方式告诉你 NN 是多少:假设 p1=2,p2=3,p_1=2,p_2=3,\dots 为从小到大的所有质数,巡会给你 kk 和长度为 kk 的数组 a1,a2,,aka_1,a_2,\dots,a_k 代表 N=p1a1×p2a2×pkakN=p_1^{a_1}\times p_2^{a_2}\dots\times p_k^{a_k}

巡很好奇有多少对正整数对 (a,b)(a,b) 满足 a2b2=Na^2-b^2=N。你只需要告诉巡这个数量的两倍109+710^9+7 取模即可。

输入格式

第一行一个正整数 TT 表示测试点个数。

对于每个测试数据,第一行一个正整数表示 kk

接下来一行 kk 个非负整数表示 aia_i

输出格式

对每个测试用例,输出一行一个非负整数表示答案

样例 1

【样例输入】

2
2
1 1
2
2 1

【样例输出】

0
2

【样例解释】

对第一组测试样例,N=21×31=6N=2^1\times 3^1=6。可以证明没有这样的 (a,b)(a,b)

对第二组测试样例,N=22×31=12N=2^2\times 3^1=12。有一组解 (4,2)(4,2)

再次提醒,我们需要输出的是答案的两倍对 109+7\bm {10^9+7} 取模的结果。

样例 2

见下发 sqrt2.in/ans\textit{sqrt2.in/ans}

样例满足测试点 11 的性质。

数据范围

对所有数据,保证 1T10001\leq T\leq 10001k1001\leq k\leq 1000ai<109+70\leq a_i< 10^9+7

测试点编号 TT\leq kk\leq 特殊性质
11 1010 55 0ai20\leq a_i\leq 2
22 10001000 100100 aia_i[0,109+7)[0,10^9+7) 中随机生成
3,43,4

NOIP 2024 模拟赛(三)

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2024-8-8 8:00
End at
2024-8-8 12:00
Duration
4 hour(s)
Host
Partic.
38