hdu 5833 || ccpc 2016 网络赛 1002 Zhu and 772002 (高斯消元)
Aug 14, 2016 · 2 min read · math 高斯消元
hdu 5833 题目链接 题意:n个数,保证每个数的素因子不超过2000,从中取若干个,问乘积是完全平方数的方案数. 思路: 完全平方数就是要求每个质因子的指数是偶数次. 列方程组,a1,a2,a3......am分别表示bi是否在集合中.对于每一个素因子,建立异或方程组,要求因子个数为偶数,即异或为0 然后得到自由元的个数为num,答案为2^num-1 (减去空集) #include <iostream> #include <string.h