乘积是平方数

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 square1.in 输出文件 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