Zhu and 772002
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5833
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.
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.
2
3
3 3 4
3
2 2 2
Sample Output
Case #1:
3
Case #2:
3
Source
2016中国大学生程序设计竞赛 - 网络选拔赛
##题意:
给出n个数,求有多少种方式使得选取的数的乘积是一个完全平方数.
##题解:
原题:[UVA11542](http://acm.hust.edu.cn/vjudge/problem/34393) (大白书P160例题25)
转化成异或方程组,并用高斯消元求解矩阵的秩.
很遗憾,上述知识点都不会....
##代码:
``` cpp
#include
#include
#include
#include
#include
#include
#include