极大线性无关组

题目大意

给你n（<=300）个最大质因数不超过2000的数x（x<=10^18） 求从中选取若干个数乘积为完全平方数的方案数

思路

选取的数因式分解后每个质因数的出现偶数次

问题

如何维护当前数能否与之前的数相乘得到完全平方数呢 必选当前的数对答案的贡献如何统计呢

题解

将每个数因式分解后用01串表示，维护当前极大线性无关组 若当前的数能由极大线性无关组得到，则当前的数与极大线性无关组凑成的0可以加入任意一个答案集合（贡献为ans），也可以不加入任何一个原有答案集合（贡献为1），则加入该元素后答案数为ans*2+1 否则将当前01串加入线性无关组

题目

hdu5833