首页 > 代码库 > UVa11542
UVa11542
11542 Square
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 f4,6,10,15g
there are 3 such subsets. f4g, f6,10,15g and f4,6,10,15g. 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 1015. 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 t
into signed 64 bit integer.
Sample Input
4
3
2 3 5
3
6 10 15
4
4 6 10 15
3
2 2 2
Sample Output
0
1
3
3
题意：
给出n个整数，从中选出1个或者多个，使得选出的整数乘积是完全平方数，一共有多少种选法。该题输入的数的素因子都不超过500。
分析：
注意到“不含大于500的素因子”这一条件，我们将考虑每一个数的唯一分解式，并将其表示为01向量。具体来说，考虑一个矩阵，其中的元素(i,j)=1/0（i行j列）表示对于第j个整数，它第i个素因子的幂次是奇数/偶数。于是输入的n个数就可以被表示成这样一个m行n列的0/1矩阵。设这个矩阵是A。设一个解向量（列向量）X=(x1,x2,x3,…,xn)(xi = 1或者0,i = 1,2,…,n)。解向量的分量xi = 1表示要选取第i个数，反之不选。于是，选取一些数的乘积是完全平方数等价于AX=0(mod2)。在mod 2的情况下为A的增广矩阵消元是容易的，这是因为，不需要做乘法和除法，每次只需要做的就是异或，每次也不需要找到绝对值最大的系数ari，任意一个ari = 1即可实现消元。
最后，假设消元后发现自由变元有f个，则线性方程的解一共有2^f。注意本题不能一个数都不选，所以，最终的答案需要减去1。即答案是2^f-1。f的值可以通过求系数矩阵的秩求得。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <iostream> 6 using namespace std; 7 const int maxn = 500; 8 const int maxp = 100; 9 const int MOD = 1e9;10 typedef long long LL;11 int vis[maxn + 1]; //vis[i] = 1是合数、vis[i] = 0是素数或者112 int prime[maxp + 1];13 // 筛素数14 void sieve(int n){15 int m = (int)sqrt(n + 0.5); // 避免浮点误差16 memset(vis,0,sizeof vis);17 for(int i = 2 ; i <= m ; i++) if(!vis[i])18 for(int j = i * i ; j <= n ; j += i) vis[j] = 1;19 }20 // 生成素数表，放在prime数组中，返回素数的个数21 int gen_primes(int n){22 sieve(n);23 int c = 0;24 for(int i = 2 ; i <= n ; i++)if(!vis[i])25 prime[c++] = i;26 return c;27 }28 typedef int Matrix[maxn + 1][maxn + 1];29 // 一共m个方程，n个变量30 int _rank(Matrix A,int m,int n){ // m行n列的01矩阵求秩，同时消元31 int i = 0,j = 0,k,r,u;32 while(i < m && j < n){ // 当前正在处理第i个方程、第j个变量33 r = i;34 for(k = i ; k < m ; k++)if(A[k][j]){35 r = k;36 break;37 }38 if(A[r][j]){39 if(r != i)for(k = 0 ; k <= n ; k++)swap(A[r][k],A[i][k]);40 // 消元后第i行第一个非零列是第j列，且u>i行的第j列均为041 for(u = i + 1 ; u < m ; u++) if(A[u][j])42 for(k = i ; k <= n ; k++) A[u][k] ^= A[i][k];43 i++;44 }45 j++;46 }47 return i;48 }49 Matrix A;50 int main(){51 int m = gen_primes(maxn);52 int T; scanf("%d",&T);53 while(T--){54 int n,_maxp = 0; scanf("%d",&n);55 long long x;56 memset(A,0,sizeof A);57 for(int i = 0 ; i < n ; i++){58 scanf("%lld",&x);59 for(int j = 0 ; j < m ; j++)60 while(x % prime[j] == 0){61 _maxp = max(_maxp,j);62 x /= prime[j];63 A[j][i] ^= 1;64 }65 }66 int r = _rank(A,_maxp + 1,n); // 只用到了前_maxp+1个素数67 printf("%lld\n",(1LL << (n - r)) - 1); // 空集不是解所以减168 }69 return 0;70 }
UVa11542