题目链接
题解
完全平方数有因子的偶数次幂乘积构成
对于因数个数这就构成了%2意义下的方程组，对于因子列异或方程组
求自由元的自由组合方案数
因为不是很熟悉bitset加上hdu巨坑评测机，然后调了一下午？
代码
#include<bits/stdc++.h>
using namespace std; // 每天好心情从namespace开始
const int maxn = 157;
#define LL long long
inline LL read() {
LL x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')f = - 1; c = getchar();}
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
int n;
const int mod = 1000000007;
long long A[100007];
int prime[100007],is[100007],num = -1;
void getprime() {
for(int i = 2;i <= 2000;++ i) {
if(!is[i]) prime[++ num] = i;
for(int j = 0;j <= num && prime[j] * i <= 2000;++ j) {
is[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
bitset<330>a[305];
int guass(int equ,int var) {
int r,c,t,j = 0;
for(r = c = 0;r < equ && c < var;++ r, ++c) {
for(t = r;t < equ;++ t) if(a[t][c]) break;
if(t == equ) {
r --;continue;
} else swap(a[t],a[r]);
for(int i = r + 1; i < equ;++ i) if(a[i][c]) a[i] ^= a[r];
}
return var - r;
}
int solve() {
for(int i = 0; i < 305; i++) a[i].reset();
for(int i = 0;i < n;++ i)
for(int j = 0;j <= num;++ j) {
LL tmp = A[i];
if(tmp % prime[j] == 0) {
bool flag = 0;
while(tmp % prime[j] == 0) {
tmp /= prime[j];
flag ^= 1;
}
a[j][i] = flag;
}
}
int zyy = guass(num + 1,n);
LL ret = 1;
for(int i = 1;i <= zyy;++ i)ret <<= 1,ret %= mod;
return ret - 1;
}
int main() {
getprime();
int t = read();
int cas = 0;
while(t --) {
++ cas;
printf("Case #%d:\n",cas);
n = read();
for(int i = 0;i < n;++ i) A[i] = read();
printf("%d\n",solve());
}
return 0;
}