题意：
有N(n<=1000)个数 a1,a2,..,an, ai <= 10^15, 取其中部分组合相乘的到数是一个完全平方数.求方案总数.
其中保证 ai 不包含大于500的质因子.
解题思路:
解决本题需要有,线性代数基础. 涉及到关于矩阵的初等变换与高斯消元.求解齐次方程.
首先考虑,一个数 x = p1^e1 * p2^e2 * ... * pn^en
若其是一个完全平方数,则 所有的 ei % 2 == 0 .
另外. 取部分数相乘. 例如三个数 ai*aj*ak = x ,此时我们只关心的是其
对应的质因子的幂皆为偶数. 所以对于 ai = p1^e1 * p2^e2 * ... * pk*ek 而言.
我们只需要知道对应的 ( e1, e2, e3, ... , ek )的奇偶性就可以了.
假定其 ei = 0, 则其为 偶数, ei = 0, 则其为 奇数.
则对于每一个数字, 我们都可以用一个 01向量表示, 因为题目已说明,不同质因子不会超过500.
通过素数筛选500以内质数,发现其不超过88个.设其为m个, 所以我们得出, 对于每一个数 ai ,我们都可以用一个 88维的01列向量表示.
而对于 n 个数. 则有 n个 列向量来表示
| a11, a12, ...,a1n |
| a21, a22, ...,a2n |
| ... |
| am1,am2,...,amn |
假设其为 A, 则有一个n维列向量向量 x (x1,x2,..,xn),其中 xi 表示第i个数取还是不取,所以 xi = 0 or 1.
更直观的反映是, 若 xi = 0, 则代表着第i个数不取, 意味着第对于矩阵A而言, 第j列的值与 N维列向量计算厚皆为0.
使其得到 一个 m维列向量 b( b1,b2,...,bm ),形式如下
A*x = b .
其中 b ( b1,b2, ..., bm ) 即代表着 组合的数, res = p1^e1 * p2^e2 * ... * pm*em, 其 (e1, e2, .., em) 是否对应
位置是否为偶数, 例如 bi = 0, 则 ei 为偶数, bi = 1, ei 为奇数.
若要保证 res 是一个完全平方数, 则 b( b1, b2, ..., bm ) 必须为 b(0,0,...,0) 所以得到了一个齐次方程组.
通过高斯消元.得出此矩阵的秩 r, 则此时秩的含义是, 有r个未知量xi能够确定.
此时还有 n-r个未知量是不确定. 而 xi 的取值只有 0 or 1. 则此时解的方案数为 2^(n-r) ,
另外, 当 n-r个未知量都为空时, 不满足题目要求. 所以需要减去1, 去掉空集的情况.
View Code
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; typedef int Matrix[N][N]; typedef long long LL; int pre[N],vis[N]; int getprime(int x){ memset(vis,0,sizeof(vis)); vis[1] = 1; int cnt = 0; for(int i = 2; i <= x; i++){ if( vis[i] == 0 ) pre[cnt++] = i; for(int j = 0; j < cnt && i*pre[j] <= x; j++){ vis[ i*pre[j] ] = 1; if( i%pre[j] == 0 ) break; } } return cnt; } //m个方程n个变量 int rank(Matrix A, int m, int n) { int i = 0, j = 0; while( i < m && j < n ){ int r = i; //目前处理第i行，j列，寻找j列不为0的行r for(int k = i; k < m; k++) if( A[k][j] ){ r = k; break; } if( A[r][j] ){//若找到 if( r != i ) //若不是i，则初等变换，交换(i,r)行 for(int k = 0; k < n; k++) swap( A[i][k] , A[r][k] ); for(int u = i+1; u < m; u++){ if( A[u][j] ) for(int k = j; k < n; k++) A[u][k] ^= A[i][j]; } i++; //处理下一行 } j++; //处理下一列 } return i; } int main(){ int T, cnt = getprime(500); scanf("%d", &T); while( T-- ){ int n, m = 0; scanf("%d", &n); LL x; Matrix A; memset(A,0,sizeof(A)); for(int i = 0; i < n; i++){ scanf("%lld", &x ); for(int j = 0; j < cnt && x >= pre[j]; j++){ while( x%pre[j] == 0 ){ m = max( m, j ); A[j][i] ^= 1; x /= pre[j]; } } } int r = rank( A, m+1, n ); printf("%lld\n", (1LL<<(n-r)) - 1 ); } return 0; }