CF895C Square Subsets

tony102

2021 年 08 月 25 日

1811 次浏览

暂无评论

535字数

题解

[Link](https://www.luogu.com.cn/problem/CF895C)

## Sol

一个完全平方数分解质因数之后每个质因子都出现偶数次

一看 $a_i \leq 70$，质因子特别少，直接变成水题。用一个 `bitset` 之类的二进制数的第 $i$ 位表示第 $i$ 个质因子是否出现过。插到线性基中，两个数相乘就是线性基中的元素异或起来。

最终的答案就是记线性基中的数 $cnt$，$ans = 2^{n - cnt} - 1$

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 1e5 + 5;
const LL mod = 1e9 + 7;

int n, tot;
int isnPri[SIZE], pri[SIZE], bit[SIZE], a[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void insert(int x) {
    for (int i = 19; i; -- i) {
        if ((1 << i) & x) {
            if (!bit[i]) { bit[i] = x; break; }
            x ^= bit[i];
        }
    }
}

LL qPow(LL a, LL b) {
    LL ans = 1ll;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

int main() {
    // freopen("code.in", "r", stdin);
    n = read(); int mx = 0;
    for (int i = 1; i <= n; ++ i) a[i] = read(), mx = std::max(mx, a[i]);
    isnPri[1] = 1;
    for (int i = 2; i <= mx; ++ i) {
        if (!isnPri[i]) pri[++ tot] = i;
        for (int j = 1; j <= tot && i * pri[j] <= mx; ++ j) {
            isnPri[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
    for (int i = 1; i <= n; ++ i) {
        int x = a[i], num = 0, opt = 0;
        for (int j = 1; j <= tot; ++ j) {
            if (x % pri[j]) continue;
            opt = 0;
            for ( ; !(x % pri[j]); opt ^= 1, x /= pri[j]);
            num |= (opt << j);
        }
        insert(num);
    }
    int cnt = 0;
    for (int i = 1; i <= 19; ++ i) {
        if (bit[i]) ++ cnt;
    }
    printf("%lld\n", qPow(2ll, n - cnt) - 1ll);
    return 0;
}
```

最后修改：2021 年 08 月 25 日