題目描述:

給出n個整數，從中選出1個或多個，使得選出的整數的乘積是完全平方數。問一共有多少種選法。
?

輸入格式:

輸入第一行為一個整數t，即測試數據的數量。
每組數據包含兩行，第一行為整數n，第二行包含n個整數。

輸出格式:

對于每組數據，輸出方案總數。
答案對109?+ 7取模。

樣例輸入:

1 4 4 6 10 15

樣例輸出:

3

提示:

對于100%的數據，1 ≤ t ≤ 30，1 ≤ n ≤ 100，所有整數均不小于1，不大于1015，且不含大于500的素因子。

時間限制: 1000ms
空間限制: 256MB

代碼如下：

#include<bits/stdc++.h> using namespace std; typedef long long ll; int a[105][105]={0},n,m=0; ll b[105]; bool x[505]={0}; void f(){for(int i=2;i<=500;i++) if(!x[i])for(int j=2;j*i<=500;j++){x[j*i]=1;}for(int i=2;i<=500;i++){if(!x[i]){b[++m]=i;}} } ll mm(){int i=1,j=1;while(i<=n&&j<=m){int r=i;for(;r<=n;r++){if(a[r][j]){break;}} if(r<=n){for(int k=0;k<=m;k++){swap(a[i][k],a[r][k]);}for(int ii=0;ii<=n;ii++) if(a[ii][j]&&ii!=i)for(int jj=0;jj<=m;jj++){a[ii][jj]^=a[i][jj];}i++;}j++;}for(int k=i;k<n;k++) if(a[k][m])return 0;return (ll)1<<(n-i+1); } int main(){int T;cin>>T;f();while(T--){ll x;cin>>n;memset(a,0,sizeof(a));for(int i=1;i<=n;i++){cin>>x;for(int j=1;j<=m;j++){while(x%b[j]==0){a[i][j]^=1;x/=b[j];}}}cout<<mm()-1<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的平方数(高斯消元）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。