高斯消元-異或線性方程組,數論-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;
}