给你n个数 选出一些数 他们的乘积是完全平方数 求有多少种方案

每个数分解因子 每隔数可以选也可以不选 0 1表示 然后设有m种素数因子 选出的数组成的各个因子的数量必须是偶数

组成一个m行和n列的矩阵 每一行代表每一种因子的系数 解出自由元的数量

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int MAXN = 1010;
const int mod = 1000000007;
typedef int Matrix[MAXN][MAXN];
typedef long long LL;
int prime[MAXN];
bool is_prime[MAXN];
int tol;
Matrix a;
LL pow_mod(LL a, LL p, LL n)
    LL ans = 1;
    while(p)
        if(p&1)
            ans *= a;
            ans %= n;
        a *= a;
        a %= n;
        p >>= 1;
    return ans;
void find_prime()
    memset(is_prime,false,sizeof(is_prime));
    tol=0;
    is_prime[1]=1;
    for(int i=2; i<MAXN; i++)
        if(!is_prime[i])
            prime[tol++]=i;
        if(!is_prime[i])
            for(int j=i*2; j<MAXN; j+=i)
                is_prime[j]=1;
int Gauss(int equ, int var)
    int max_r,col,k;
    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)
            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];
    return var-k;
int main()
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    find_prime();
    int T;
    cin>>T;
    for(int cas=1; cas<=T; cas++)
        memset(a,0,sizeof(a));
        int n;
        cin>>n;
        int var=0;
        for(int i=0; i<n; i++)
            LL x;
            cin>>x;
            for(int j=0; j<tol&&x>=prime[j]; j++)
                while(x%prime[j]==0)
                    var=max(var,j+1);
                    x/=prime[j];
                    a[j][i]^=1;
        int rk=Gauss(var,n);
        printf("Case %d: %lld\n",cas,pow_mod(2,rk,mod)-1);
    return 0;
                    给你n个数 选出一些数 他们的乘积是完全平方数 求有多少种方案每个数分解因子 每隔数可以选也可以不选 0 1表示 然后设有m种素数因子 选出的数组成的各个因子的数量必须是偶数组成一个m行和n列的矩阵 每一行代表每一种因子的系数 解出自由元的数量
				
以 杭电zhu and 772002 为例，看高斯消元如何使用
矩阵的秩等于矩阵线性无关的列的数量，自由度 = 矩阵列数 - 矩阵的秩。摘自贴吧。
线性代数，忘了。好像是通过行变换，得到一个上三角矩阵，求出某一变元的解，然后回迭求解。
下面是个例子：
#define _CRT_SECURE_ON_WARNINGS
#include 
#include 
#include 
高斯消元法(Gaussian elimination)是求解线性方阵组的一种算法，它也可用来求矩阵的秩，以及求可逆方阵的逆矩阵。它通过逐步消除未知数来将原始线性系统转化为另一个更简单的等价的系统。它的实质是通过初等行变化(Elementary row operations)，将线性方程组的增广矩阵转化为行阶梯矩阵(row echelon form).
已知线性方程组:
				
请教了比利 
首先 2n2^n 次项是没有问题的，比如2√+3√\sqrt2+\sqrt3，可以构造f(x)=(x+2√+3√)(x+2√−3√)(x−2√+3√)(x−2√−3√)f(x)=(x+\sqrt2+\sqrt3)(x+\sqrt2-\sqrt3)(x-\sqrt2+\sqrt3)(x-\sqrt2-\sqrt3) 
这个不是最优解 
最优解应该是构造这样一个矩阵 每一行代表一个质因子
基本思想是通过将增广矩阵经过行初等变化变成简化阶梯形矩阵。
下面采用的是列主元高斯消元法，复杂度为O(n^3)。
很容易根据高斯消元法的过程得出行列式和秩的算法。
/*********************************************************
*            -...