题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5833 ——————————-. 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中国大学生程序设计竞赛 - 网络选拔赛
———————————————-.
题目大意： 就是有n这么长的序列 然后从中选至少一个数 让这些数的乘积为完全平方数 问有多少种选法
题目分析： 首先注意题目说的 a[i]的最大质因子不会超过2000 这也是在提示你要质因子分解 分解就简单处理一下分解就行了 怎么分都行 这里首先想到的就应该是算数基本定理 A=p1^a1*p2^a2*p3^a3*…*pn^an (pn是质数) 然后分解的时候怎么怎么存储数据?,怎么操作呢? 首先要想这个问题 几个数相乘的结果如果是完全平方数 有什么特点呢? 说白了就是开方后能得到一个整数 比如说B=a1*a2; B,a1,a2都为整数 且a1==a2 那么a1和a2 他们质因子分解后是完全一样的 那么B的算是基本定理展开就等于a1的算是基本定理展开乘上a2的算是基本定理展开 那么可以肯定的是B的算是基本定理展开 an一定是偶数的 所以就能拆成两个a1 a2 那么反过来说只要B的算是基本定理展开 an都是偶数 就一定是完全平方数 那么在判断的时候就只要判断an的值的奇偶性就可以了 于是我们就开了这样的数组factor[n+10][333] (2000以内的质数只有303个) 把每个数转化为了一个2进制数 我们可以把题目转化成求n个数中的k个数数异或为0的情况数。使用x1—xn表示最终第i堆石子到底取不取（1取，0不取），将每堆石子数画成2进制的形式，列成303个方程来求自由变元数，最后由于自由变元能取1、0两种状态 然后直接高斯消元就可以了 最后的结果就是 2^(自由元)-1
注: 最终结果减去的那个一 减去的是1个都不选则情况下的0
附本题代码 ———————————–.
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <map> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int MOD = 1000000007; #define weishu k int prime[50000]; int Is_or[20100]; int k; void Prime() { int n=2001; k=0; memset(Is_or,1,sizeof(Is_or)); Is_or[0]=Is_or[1]=0; for(int i=2; i<n; i++) { if(Is_or[i]) { prime[k++]=i; for(int j=i+i; j<n; j+=i) { Is_or[j]=0; } } } return ; } LL a[333]; LL g[333][333]; int Gauss(int n) { int i, j, r, c, cnt; for (c = cnt = 0; c < n; c++) { for (r = cnt; r < weishu; r++) { if (g[r][c]) break; } if (r < weishu) { if (r != cnt) { for (i = 0; i < n; i++) { g[r][i]^=g[cnt][i]; g[cnt][i]^=g[r][i]; g[r][i]^=g[cnt][i]; } } for (i = cnt + 1; i < weishu; i++) { if (g[i][c]) { for (j = 0; j < n; j++) g[i][j] ^= g[cnt][j]; } } cnt++; } } return n - cnt; } LL qmod (LL a,LL b) { LL res = 1; while(b) { if(b&1) res=(res*a)%MOD; b >>= 1; a=(a*a)%MOD; } return res; } int main() { Prime(); int c,p=0; int n, i, j; scanf("%d", &c); while (c--) { int fuck = 0; scanf("%d", &n); memset(g,0,sizeof(g)); LL temp; for(int i=0; i<n; i++) { scanf("%I64d",&a[i]); temp=a[i]; for(int j=0; j<k; j++) { if(temp<prime[j]) break; while(temp%prime[j]==0) { temp/=prime[j]; g[j][i]++; } g[j][i]%=2; } } LL ans, vary; vary = Gauss(n); printf("Case #%d:\n",++p); ans = qmod(2,vary); printf("%I64d\n",(ans-1)%MOD); } return 0; }