题目名称	1498. [UVa 11542] 乘积是平方数
输入输出	`square1.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cstdio 于2014-01-20加入
开放分组	全部用户
提交状态
分类标签	UVa 高斯消元法线性基
	分享题解

通过：13，提交：41，通过率：31.71%
yuan	100	0.000 s	0.00 MiB	C++
op_组撒头屯	100	0.000 s	0.00 MiB	C++
清羽	100	0.024 s	0.49 MiB	C++
ZXCVBNM_1	100	0.035 s	0.41 MiB	C++
wsy	100	0.044 s	1.29 MiB	C++
真呆菌	100	0.044 s	1.31 MiB	C++
Ninaye	100	0.055 s	1.31 MiB	C++
Ninaye	100	0.061 s	1.31 MiB	C++
真呆菌	100	0.064 s	1.31 MiB	C++
sxysxy	100	0.067 s	1.25 MiB	C++

本题关联比赛
2022级数学专题练习赛1

关于乘积是平方数的近10条评论(全部评论)
不能用一个64位整数一压了事……（其实是没看到白书上的“每32位一压”！）对于运算符"<<"，如果参数是int的话那么答案也会是int……所以要用64位类型的1，具体方法见代码另外，由于“不超过500”的限制，因此我随机出来的数据有点大（否则会半天随机不出来）……将就着用吧…… cstdio 2014-01-20 21:08 1楼

1498. [UVa 11542] 乘积是平方数

★★ 输入文件：square1.in 输出文件：square1.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

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

【输入格式】

输入包含多组数据。

输入文件的第 $1$ 行是一个整数 $T(1 \leq T \leq 30)$，表示测试数据组数。

接下来是 $T$ 组测试数据，每组占 $2$ 行：

第 $1$ 行是一个整数 $n(1 \leq n \leq 100)$。

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

【输出格式】

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

【样例输入】

【样例输出】

【来源】

UVa 11542 Square

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

Problemsetter: Abdullah al Mahmud

Special Thanks to: Manzurur Rahman Khan