乘积是平方数

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file square1.in Output file square1.out

【题目描述】

给出n个整数,那么它们组成的集合有2^n-1个子集。请你计算其中有多少个子集,其中的所有元素之积是完全平方数。例如,集合{4,6,10,15}有三个这样的子集:{4},{6,10,15}和{4,6,10,15}。完全平方数是指平方根为整数的数。例如1,4,9,16,...

【输入格式】

输入包含多组数据。

输入文件的第1行是一个整数T(1<=T<=30),表示测试数据组数。

接下来是T组测试数据,每组占2行:

第1行是一个整数n(1<=n<=100)。

第2行是n个正整数,由空格分隔。这些正整数在区间[1,10^15]内。它们都不含超过500的素因子。

【输出格式】

对每组测试数据,输出一行:所有元素乘积为完全平方数的子集个数。

【样例输入】

4

3

2 3 5

3

6 10 15

4

4 6 10 15

3

2 2 2

【样例输出】

0

1

3

3

【来源】

UVa11542 Square

刘汝佳,《算法竞赛入门经典训练指南》表2-12

Problemsetter: Abdullah al Mahmud

Special Thanks to: Manzurur Rahman Khan