111qqz的小窝

差不多已经是个废喵了

hdu 5833 || ccpc 2016 网络赛 1002 Zhu and 772002 (高斯消元)

hdu 5833 题目链接

题意:n个数,保证每个数的素因子不超过2000,从中取若干个,问乘积是完全平方数的方案数。

思路: 完全平方数就是要求每个质因子的指数是偶数次。

列方程组,a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子,建立异或方程组,要求因子个数为偶数,即异或为0

然后得到自由元的个数为num,答案为2^num-1 (减去空集)

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz