Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n个数，保证每个数的素因子不超过2000，从中取若干个，问乘积是完全平方数的方案数。
思路： 完全平方数就是要求每个质因子的指数是偶数次。
列方程组，a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子，建立异或方程组，要求因子个数为偶数，即异或为0
然后得到自由元的个数为num，答案为2^num-1 (减去空集)
代码实现
1#include <iostream>
2#include <string.h>
3#include <math.h>
4#include <queue>
5#include <algorithm>
6#include <stdlib.h>
7#include <map>
8#include <set>
9#include <stdio.h>
10using namespace std;
11typedef long long LL ;
12#define pi acos(-1.0)
13const int mod=1e9+7;
14const int INF=1e9;
15const double eqs=1e-9;
16const int N=310;
17LL mat[N][N], a[N], equ, var, prime[N];
18LL c[N];
19LL gauss()
20{
21 LL i, j, k, h, max_r, tmp;
22 for(i=0,j=0;i<equ&&j<var;i++,j++){
23 max_r=i;
24 for(k=i+1;k<equ;k++){
25 if(mat[k][j]>mat[max_r][j]) max_r=k;
26 }
27 if(max_r!=i){
28 for(k=j;k<=var;k++){
29 swap(mat[i][k],mat[max_r][k]);
30 }
31 }
32 if(mat[i][j]==0){
33 i--;
34 continue ;
35 }
36 for(k=i+1;k<equ;k++){
37 if(mat[k][j]==0) continue ;
38 for(h=j;h<=var;h++){
39 mat[k][h]^=mat[i][h];
40 }
41 }
42 }
43 tmp=i;
44 //printf("%d\n",tmp);
45 for(;i<equ;i++){
46 if(mat[i][var]){
47 return 0;
48 }
49 }
50 return var-tmp;
51}
52void output(int k)
53{
54 LL i, j, x, y, tmp;
55 memset(c,0,sizeof(c));
56 c[0]=1;
57 x=0;
58 for(i=0;i<k;i++){
59 for(j=0;j<=80;j++){
60 y=(c[j]*2+x);
61 x=(c[j]*2+x)/10;
62 c[j]=y;
63 }
64 }
65 for(i=80;i>=0;i--){
66 if(c[i]){
67 tmp=i;
68 break;
69 }
70 }
71 c[0]--;
72 for(i=tmp;i>=0;i--){
73 printf("%lld",c[i]);
74 }
75 puts("");
76}
77void init()
78{
79 LL i, j, cnt=0, flag;
80 for(i=2;;i++){
81 flag=0;
82 for(j=2;j*j<=i;j++){
83 if(i%j==0){
84 flag=1;
85 break;
86 }
87 }
88 if(!flag){
89 prime[cnt++]=i;
90 }
91 if(cnt==305) return ;
92 }
93}
94LL ksm(LL a,LL b)
95{
96 LL res = 1LL;
97 while (b>0)
98 {
99 if (b&1)
100 res = (res*a)%MOD;
101 b = b/2;
102 a = (a*a)%MOD;
103 }
104
105 return res;
106}
107
108int main()
109{
110
111 // freopen("code/in.txt","r",stdin);
112 LL t, n, i, j, x, cnt, ans;
113 int T;
114 cin>>T;
115 int cas = 0 ;
116 while (T--){
117 printf("Case #%d:\n",++cas);
118 init();
119 scanf("%lld",&n);
120 t = 305;
121 for(i=0; i<n; i++) {
122 scanf("%lld",&a[i]);
123 }
124 for(i=0; i<n; i++) {
125 x=a[i];
126 for(j=0;j<t;j++){
127 cnt=0;
128 while(x%prime[j]==0){
129 cnt++;
130 x/=prime[j];
131 }
132 mat[j][i]=(cnt&1);
133 }
134 }
135 for(i=0;i<t;i++){
136 mat[i][n]=0;
137 }
138 equ=t;
139 var=n;
140 ans=gauss();
141 if(ans)
142 printf("%lld\n",ksm(2,ans)-1);
143 else puts("0");
144 }
145 return 0;
146}