HDU 5833 Zhu and 772002

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

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.

Zhu和772002都擅长数学。某天，Zhu想试试772002的能耐，就给772002出了道数学题。

但772002与女票有约在先，果断甩锅予你。

有n个数a1,a2,...,an。每个数的质因数不超过2000，你可以选择至少一个数并将所选的数相乘，得到b。

有多少种选择方式可以使b为完全平方数。结果可能非常大，输出时模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≤10¹⁸).

第一行是一个整数T(T≤100)，表示有T个测试用例的数量。

对于每个测试用例：

第一行有一个整数n(1≤n≤300)，下一行有n个数a1,a2,...,an,(1≤ai≤10¹⁸)。

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.

对于第i个测试用例，先输出一行Case #i:。

然后输出第i个测试用例的答案模1000000007后的结果。

Sample Input - 输入样例	Sample Output - 输出样例
2 3 3 3 4 3 2 2 2	Case #1: 3 Case #2: 3

【题解】

　　分解质因数 + 高斯消元

　　对于容易一个输入的数进行分解质因数，保存到矩阵的各个行中。

　　每个数都能看作若干个质数相乘，若每个质数的指数均为偶数，这个数即是完全平方数。因此用10表示奇偶，每个数的合并/化简就能用异或来操作。

　　然后用异或高斯消元，得到矩阵的秩r，接着得到（n - r）个可*组合的完全平方数。最后组合数求和，去掉什么都不选的情况，结果为2ⁿ- 1。

　　（啪！迷之巴掌）

　　好吧，其实我一开始根本不知道高斯消元是什么鬼。刚刚开始的理解就是分解质因数（形成多项式），压入矩阵方便求基底（当成向量来看），然后默默地发现高斯消元就是矩阵化简吧……

【代码 C++】

 #include <cstdio>

 #include <cstring>

 #define pMX 2005

 #define  mod 1000000007

 int prim[] = {  }, iP, mtx[][];

 void getPrim() {

     int i, j;

     bool mark[pMX];

     memset(mark, , sizeof(mark));

     for (i = ; i < pMX; i += ) {

         if (mark[i]) continue;

         prim[++iP] = i;

         for (j = i << ; j < pMX; j += i) mark[j] = ;

     }

 }

 void tPrim(int y, __int64 a) {

     int i, j;

     for (i = ; i <= iP && a >= prim[i]; ++i) {

         if (a / prim[i] * prim[i] == a) {

             for (j = ; a / prim[i] * prim[i] == a; a /= prim[i]) ++j;

             mtx[y][i] = j & ;

         }

     }

 }

 int mTS(int n){

     bool inUS[]; memset(inUS, , sizeof(inUS));

     int size = , i, j, k, ik;

     for (j = ; j <= iP; ++j){

         for (i = ; i < n; ++i){

             if (inUS[i] ==  && mtx[i][j] == ) break;

         }

         if (i == n) continue;

         inUS[i] = ; ++size;

         for (k = ; k < n; ++k){

             if (inUS[k] || mtx[k][j] == ) continue;

             for (ik = j; ik <= iP; ++ik) mtx[k][ik] ^= mtx[i][ik];

         }

     }

     return n - size;

 }

 __int64 qMod(__int64 a, int n){

     __int64 opt = ;

     while (n){

         if (n & ) opt = (opt*a) % mod;

         n >>= ;

         a = (a*a) % mod;

     }

     return opt;

 }

 int main() {

     getPrim();

     int t, iT, i, n;

     __int64 ai;

     scanf("%d", &t);

     for (iT = ; iT <= t; ++iT) {

         printf("Case #%d:\n", iT);

         memset(mtx, , sizeof(mtx));

         scanf("%d", &n);

         for (i = ; i < n; ++i){

             scanf("%I64d", &ai);

             tPrim(i, ai);

         }

         printf("%I64d\n", qMod(, mTS(n)) - );

     }

     return ;

 }

秒客网

HDU 5833 Zhu and 772002

HDU 5833 Zhu and 772002

相关文章