Tony102's Blog - 线性基
type: channel
link: https://tony102.com/index.php/tag/%E7%BA%BF%E6%80%A7%E5%9F%BA/
items: CF895C Square Subsets

CF895C Square Subsets
type: item
date: 2021-08-25T21:58:00+08:00
description: LinkSol一个完全平方数分解质因数之后每个质因子都出现偶数次一看 $a_i \leq 70$，质因子特别少，直接变成水题。用一个 bitset 之类的二进制数的第 $i$ 位表示第 $i$ 个质因子是否出现过。插到线性基中，两个数相乘就是线性基中的元素异或起来。最终的答案就是记线性基中的数 $cnt$，$ans = 2^{n - cnt} - 1$Code#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; }