高斯消元-异或线性方程组,数论-HDU5833

题目大意：

给你n个数,问你有多少种方案使得选出一个子集使得其累乘值为完全平方数.

n ≤ 300 , a i ≤ 1 e 18 且 a i 所 含 最 大 质 因 数 ≤ 2000 n \leq 300,a_i \leq 1e18且a_i所含最大质因数 \leq 2000 n≤300,ai​≤1e18且ai​所含最大质因数≤2000

题目思路:

一个数为完全平方数,那么其每个质因数的指数均为偶数

对于每个质数我们列一个异或线性方程.设 x i x_i xi​为是否选第 i i i个数.

所以我们有 n n n个未知数, π ( 2000 ) \pi(2000) π(2000)个方程.答案就是 2 f r e e 2^{free} 2free.

那 f [ i ] [ j ] f[i][j] f[i][j]的系数就是第j个数中含有 奇数个(1)还是偶数(0)个 p r i m e [ i ] prime[i] prime[i]

高斯消元求*元即可.

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1000000007;
bool isp (int x)
{
    if (x <= 3) return x >= 2;
    int g = sqrt(x + 0.5);
    for (int i = 2 ; i <= g ; i++) if (x % i == 0) return false;
    return true;
}
ll p[1000] , cnt;
ll b[305];
bitset<305> a[305];
ll ksm (ll a , ll b){ ll ans = 1 , base = a;
while (b){if (b & 1) ans = ans * base % mod;b >>= 1;base = base * base % mod;}return ans;}
int main()
{
    ios::sync_with_stdio(false);
    for (int i = 2 ; i <= 2000 ; i++){
        if (isp(i)) p[++cnt] = i;
    }
    int t; cin >> t;
    int gg = 0;
    while(t--){
        int n; cin >> n;
        for (int i = 1 ; i <= n ; i++){
            cin >>  b[i];
        }
        for (int i = 1 ; i <= cnt ; i++){
            int now = 0;
            for (int j = 1 ; j <= n ; j++){
                ll g = b[j];
                while(g % p[i] == 0){
                    g /= p[i];
                    now++;
                }
                a[i][j] = (now % 2);
            }
        }
        // guess
        int r , c , free = 0;
        for (r = c = 1 ; r <= cnt && c <= n; r++ , c++){
            int p = 0;
            for (int j = r ; j <= cnt ; j++)
                if (a[j][c]){
                    p = j;
                    break;
                }
            if (!p){
                r--;
                free++;
                continue;
            }
            swap(a[p] , a[r]);
            for (int j = 1 ; j <= cnt ; j++){
                if (j == r) continue;
                if (!a[j][c]) continue;
                a[j] ^= a[r];
            }
         }
         cout << "Case #" << (++gg) << ":" << endl;
         cout << (ksm(2ll , free) - 1 + mod)%mod << endl;
    }
    return 0;
}