[原创]hdu 5833 Zhu and 772002 2016中国大学生程序设计竞赛 - 网络选拔赛1002 [质因子分解+高斯消元]【数论】

2016-08-15 09:35:35 Tabris_ 阅读数：309

https://blog.csdn.net/qq_33184171/article/details/52208349

-------------------------------.
Zhu and 772002

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 446 Accepted Submission(s): 147

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中国大学生程序设计竞赛 - 网络选拔赛

----------------------------------------------.

A=p1^a1p2^a2p3^a3*…pn^an (pn是质数)

a2; B,a1,a2都为整数 且a1==a2

-----------------------------------.