题意，给你一堆最大质因子小于2000的数，从其中选任意个，并乘起来，有多少种方案能使乘积为完全平方数。
有原题。 方法异或方程组高斯消元。系数矩阵每个元素为某个素数在某个数里面有奇数个还是偶数个，x，代表某个数是否选中，方程组右边全是0。
仔细体会一下就会明白是怎么回事了。
用了别人的高斯消元的模板..稍微改了改....
#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<math.h> using namespace std; const int MAXN = 305; const long long MOD = 1000000007; int n; long long a[MAXN][MAXN];//系数矩阵 long long num[MAXN]; int x[MAXN];//解集 bool free_x[MAXN];//标记是否是不确定的变元 int prime[303]; inline int gcd(int a, int b) { int t; while (b != 0) { t = b; b = a%b; a = t; } return a; } inline int lcm(int a, int b) { return a / gcd(a, b)*b;//先除后乘防溢出 } int Gauss(int equ, int var) { int i, j, k; int max_r;// 当前这列绝对值最大的行. int col;//当前处理的列 int LCM; for (int i = 0; i <= var; i++) { x[i] = 0; free_x[i] = true; } //转换为阶梯阵. col = 0; // 当前处理的列 for (k = 0; k < equ && col < var; k++, col++) {// 枚举当前处理的行. // 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差) max_r = k; for (i = k + 1; i<equ; i++) { if (abs(a[i][col])>abs(a[max_r][col])) max_r = i; } if (max_r != k) {// 与第k行交换. for (j = k; j<var + 1; j++) swap(a[k][j], a[max_r][j]); } if (a[k][col] == 0) {// 说明该col列第k行以下全是0了，则处理当前行的下一列. k--; continue; } for (i = k + 1; i<equ; i++) {// 枚举要删去的行. if (a[i][col] != 0) { for (j = col; j < var + 1; j++) { a[i][j] ^= a[k][j]; } } } } return var - k; // 自由变元有var - k个. } bool isPrime(int x) { for (int i = 2; i <= sqrt(x) + 1; i++) { if (x % i == 0) return false; } return true; } void init() { int cnt = 0; prime[cnt++] = 2; for (int i = 3; i < 2000; i++) { if (isPrime(i)) prime[cnt++] = i; } } long long quickmod(long long a, long long b, long long m) { long long ans = 1; while (b)//用一个循环从右到左便利b的所有二进制位 { if (b & 1)//判断此时b[i]的二进制位是否为1 { ans = (ans*a) % m;//乘到结果上，这里a是a^(2^i)%m b--;//把该为变0 } b /= 2; a = a*a%m; } return ans; } int main(void) { init(); int T; cin >> T; for (int cas = 1; cas <= T; cas++) { memset(a, 0, sizeof a); cin >> n; for (int i = 0; i < n; i++) cin >> num[i]; for (int i = 0; i < 303; i++) { int tmp; for (int j = 0; j < n; j++) { tmp = 0; while (num[j] % prime[i] == 0) { num[j] /= prime[i]; tmp++; } a[i][j] = tmp % 2; } } long long ans = (quickmod(2, Gauss(303, n), MOD) + MOD) % MOD - 1; cout << "Case #" << cas << ":" << endl; cout << ans << endl; } return 0; }