首页 > 代码库 > uva 11542 高斯消元
uva 11542 高斯消元
Square
Input: Standard Input
Output: Standard Output
Given n integers you can generate 2n-1 non-empty subsets from them. Determine for how many of these subsets the product of all the integers in that is a perfect square. For example for the set {4,6,10,15} there are 3 such subsets. {4}, {6,10,15} and {4,6,10,15}. A perfect square is an integer whose square root is an integer. For example 1, 4, 9,16,…. .
Input
Input contains multiple test cases. First line of the input contains T(1≤T≤30) the number of test cases. Each test case consists of 2 lines. First line contains n(1≤n≤100) and second line contains n space separated integers. All these integers are between 1 and 10^15. None of these integers is divisible by a prime greater than 500.
Output
For each test case output is a single line containing one integer denoting the number of non-empty subsets whose integer product is a perfect square. The input will be such that the result will always fit into signed 64 bit integer.
Sample Input Output for Sample Input
4 3 2 3 5 3 6 10 15 4 4 6 10 15 3 2 2 2 | 0 1 3 3 |
Problemsetter: Abdullah al Mahmud
Special Thanks to: Manzurur Rahman Khan
题目大意：给n个整数，从中选1个或多个，他们的积是一个完全平方数。这样的情况有多少种？
解题思路：选s个整数出来(1<=s<=n),它们的积可以表示成a1^p1*a2.P2....an^pm,要想它是一个完全平方数，那pi必须是偶数。把每个数分解质因数，所有质因数的指数都模2，最后得出一个n*m的矩阵，进行消元，求出矩阵的秩r。那么就有n-r行每个元素都是0。从中选一行或多行（即求一个集合的真子集个数）都符合题目要求。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 typedef long long LL; 7 const int maxn=500; 8 const int maxm=105; 9 typedef int Matrix[maxm][maxm];10 int prime[maxn],num;11 bool flag[maxn];12 Matrix A;13 14 int max(int a,int b){ return a>b?a:b;}15 void swap(int& a,int& b){int t=a;a=b;b=t;}16 17 void get_primes()18 {19 int i,j;num=0;20 memset(flag,1,sizeof(flag));21 for(i=2;i<maxn;i++)22 {23 if(flag[i])prime[num++]=i;24 for(j=0;j<num&&i*prime[j]<maxn;j++)25 {26 flag[i*prime[j]]=false;27 if(i%prime[j]==0) break;28 }29 }30 }31 32 int rank(int n,int m)33 {34 int i=0,j=0,k,r,u;35 while(i<n&&j<m)36 {37 r=i;38 for(k=i;k<n;k++)39 if(A[k][j]){r=k;break;}40 if(A[r][j])41 {42 if(r!=i) for(k=0;k<=m;k++) swap(A[r][k],A[i][k]);43 for(u=i+1;u<n;u++) if(A[u][j])44 for(k=i;k<=m;k++) A[u][k]^=A[i][k];45 i++;46 }47 j++;48 }49 return i;50 }51 52 LL Pow(LL a,LL b)53 {54 LL ret=1;55 while(b)56 {57 if(b&1) ret*=a;58 a*=a;b>>=1;59 }60 return ret;61 }62 63 int main()64 {65 get_primes();66 int i,j,t,n,maxp;67 LL p;68 scanf("%d",&t);69 while(t--)70 {71 scanf("%d",&n);72 memset(A,0,sizeof(A));73 maxp=0;74 for(i=0;i<n;i++)75 {76 scanf("%lld",&p);77 for(j=0;j<num;j++)78 {79 if(p==1) break;80 while(p%prime[j]==0)81 {82 maxp=max(maxp,j);83 p/=prime[j];84 A[i][j]^=1;85 }86 }87 }88 int r=rank(n,maxp+1);89 printf("%lld\n",Pow(2,n-r)-1); 90 }91 return 0;92 }