这3道题在VJ上都可以找到,我就不放题目链接了。 还有最近HDU怎么老炸…
【UVA 11542】Square
题目大意
给你n个数字,要你从中间选出若干个数,使得他们的乘积为一个平方数。问你有多少种不同的选法。(不能一个数都不选)
题解
这一题是白书上的例题,很经典。我们设\(x_i=0\)时第i个数不选,\(x_i=1\)时选。那么我们就可以把最终的乘积表示出来: \[ {p_i}^{x_i·…·x_j}·{p_j}^{…}… \]
这个表示可能有些奇怪,其中\(p_i\)是某个质因数,而\(p_i\)的指数则是含有这个质因数的数所对应的\(x_i\),我们知道如果一个数是平方数的话他的指数必须是一个偶数。所以我们可以根据这个列出一个异或方程组,然后利用高斯消元求出自由变元的个数就行了。
代码
【POJ 1830】开关问题
题目大意
现在有若干个开关,每个开关只有两种状态,每个开关只能被操作一次,但是有些开关是会互相影响的,问你是否能达到最终状态。
题解
这个其实跟上面那题挺像的,也是对每个开关建立方程,最后高斯消元求解即可。
代码
【POJ 1222】EXTENDED LIGHTS OUT
题目大意兼题解
这题其实就是把互相影响的开关变成了互相影响的方块,同样也是对每个方块建立方程,然后求解。
注意最后的回代过程,容易求错。