HDU5833 Zhu and 772002 质因子分解 高斯消元

http://acm.hdu.edu.cn/showproblem.php?pid=5833

Danganronpa

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.

But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.

There are n numbers a1,a2,...,an. The value of the prime factors of each number does not exceed 2000, you can choose at least one number and multiply them, then you can get a number b.

How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007.

Input

First line is a positive integer T , represents there are T test cases.

For each test case:

First line includes a number n(1≤n≤300),next line there are n numbers a1,a2,...,an,(1≤ai≤1018).

Output

For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case modulo by 1000000007.

Sample Input

2
3
3 3 4
3
2 2 2

Sample Output

Case #1:
3
Case #2:
3

Author

UESTC

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

题意

给定N(N<=300)个数ai(1<=ai<=1018)。且每个数的最大质因子不超过2000。从中选出至少一个数,使它们的乘积为完全平方数,问选择的方案数。

思路

将每个数进行质因子分解,由于每个数的最大质因子不超过2000,意味着质因子只会是最小的303个质数。为每个数建立一个bitset,为bi。如果这个数有奇数个质因子p[i](p为素数表),我们就将这个数的的bitset中第i位标记为1,偶数次(包括0次)都标记为0。那么这个问题就转换成了从这些bitset中选出一些,使它们的异或值为0的方案数。假设未知量x1,x2,……,xn,其中xi∈{0,1}。那么就是求方程x1b1^x2b2……xn^bn = 0的解的个数。将bi看做列向量,就很像一个矩阵方程了。用高斯消元法求出自由元的个数k,2k-1就是最后的答案(减去什么都不选的情况)。这里可以直接把1看做自由元。此题的高斯消元,只是把普通的高斯消元的所有运算换成了异或而已。