题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5833
题意：有n个数，求选择至少一个使得它们的乘积为平方数的不同方案数。最大的质因数不超过两千。
思路：两千内的质因数有303，我们可以针对每一个质因数列一个方程，设xi为第i个数选不选，比如对于质因数2，∑xi % 2= 0( 第i个数含有2的奇数次幂方 )，偶数个质因数可以凑成平方，可以忽略。那么给定的n个数相当于n个变量，303个方程，构建303*n的矩阵进行高斯消元。最后求出自由变量的个数x，那么答案就是(2^x) - 1。最后减1是因为至少选一个数，把一个不选的方案减去。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 1000000007 const int maxn = 320; int pos[2009]; int a[maxn][maxn]; int cnt; bool check(int x) { for( int i = 2; i * i <= x; i++ ) if ( x % i == 0 ) return false; return true; } void init() { cnt = 0; rep(i,2,2000) if ( check(i) ) pos[i] = cnt++; } int solve( int m , int n ) { int i = 0 , j = 0 , k , r , u; while( i < m && j < n ) { r = i; for( k = i; k < m; k++ ) if ( a[k][j] ) {r = k;break;} if ( a[r][j] ) { if ( r != i ) for( k = 0; k <= n; k++ ) swap( a[r][k] , a[i][k] ); for( u = i + 1; u < m; u++ ) if ( a[u][j] ) for( k = i; k <= n; k++ ) a[u][k] ^= a[i][k]; i++; } j++; } return i; } LL pow_mod( LL a , int b ) { a %= mod; LL ans = 1; while( b ) { if ( b & 1 ) ans = ( ans * a ) % mod; a = ( a * a ) % mod; b >>= 1; } return ans; } int main() { init(); int T; cin>>T; rep(kase,1,T) { Clean(a,0); printf("Case #%d:\n",kase); int n; LL temp; scanf("%d",&n); rep(i,0,n-1) { scanf("%I64d",&temp); for( LL j = 2; j * j <= temp; j++ ) { if ( temp % j == 0 ) { int k = 0; while(temp % j == 0) k++ , temp /= j; if ( k & 1 ) a[pos[j]][i] = 1; } } if ( temp != 1 ) a[pos[temp]][i] = 1; } int p = n - solve( cnt , n ); printf("%I64d\n",(pow_mod(2,p)+mod-1) % mod ); } return 0; }
