hdu5833 Zhu and 772002 （高斯消元的简单应用）：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): 520    Accepted Submission(s): 174 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   题目大意：

输入n个数，范围在10的18次方以内，将其质因数分解之后他们的质因子都在2000以内，从中选出1-多个，使得所选数的乘积为完全平方数，计算一共有多少种选法。

题目分析：

不超过2000的素因子，可以考虑每个数的唯一分解式，用01向量表示一个数，再用n个01变量xi来表示我们的选择，其中xi=1表示要选第i个数，xi=0表示不选它，则可以对每个素数的幂列出一个模2的方程。

代码实现如下：

#include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> #include <math.h> using namespace std; const long long mod=1000000007; long long equ,var; long long a[330][330]; long long x[330]; long long free_x[330]; long long free_num; int Gauss() { int max_r, col, k; free_num = 0; for(k = 0, col = 0; k < equ && col < var; k++, col++) { max_r = k; for(int i = k+1 ; i < equ; i++) if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i; if(a[max_r][col] == 0) { k--; free_x[free_num++] = col; continue; } if(max_r != k) { for(int j = col; j < var+1; j++) swap(a[k][j],a[max_r][j]); } for(int i = k+1; i < equ; i++) if(a[i][col] != 0) for(int j = col; j < var+1; j++) a[i][j] ^= a[k][j]; } for(int i = k; i < equ; i++) if(a[i][col] != 0) return -1; if(k < var)return var-k; for(int i = var-1; i >= 0; i--) { x[i] = a[i][var]; for(int j = i+1; j < var; j++) x[i] ^= (a[i][j] && x[j]); } return 0; } const int MAXN = 2200; long long prime[MAXN+1]; void getPrime() { memset(prime,0,sizeof(prime)); for(int i = 2; i <= MAXN; i++) { if(!prime[i])prime[++prime[0]] = i; for(int j = 1; j <= prime[0] && prime[j] <= MAXN/i; j++) { prime[prime[j]*i] = 1; if(i%prime[j] == 0)break; } } } long long quick_mod(long long a,long long b) { long long ans=1; while(b) { if(b&1) { ans=(ans*a)%mod; b--; } b/=2; a=a*a%mod; } return ans; } long long data[330]; char str1[330],str2[330]; int main() { getPrime(); int T,m; int casenum=1; scanf("%d",&T); while(T--) { scanf("%d",&m); { for(int i = 0; i < m; i++) scanf("%lld",&data[i]); int t=303; equ = t; var = m; for(int i = 0; i < t; i++) for(int j = 0; j < m; j++) { int cnt = 0; while(data[j]%prime[i+1] == 0) { cnt++; data[j] /= prime[i+1]; } a[i][j] = (cnt&1); } for(int i = 0; i < t; i++) a[i][m] = 0; int ret = Gauss(); long long ansans=quick_mod(2,free_num); ansans=(ansans-1)%mod; printf("Case #%d:\n",casenum++); printf("%lld\n",ansans); } } return 0; }