2014年12月13日 星期六

2014/12/13 UVA 11542 - Square

/*
    學習重點:
    XOR
    高斯消去法
*/
/* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2537 */
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef int Matrix[500][500];

bool is_prime[600];
vector<int> prime;

void find_prime()
{
    fill(is_prime, is_prime+600, true);
    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i < 600; i++)
    {
        if( !is_prime[i] ) continue;

        prime.push_back(i);

        for(int j = 599/i; j >= i; j--)
            is_prime[j*i] = false;
    }
}

Matrix A;

int T, N;
long long num[200];

void process()
{

    int now = 0;

    for(int Ni = 0; Ni < N; Ni++)
    {
        int OK = 0;

        for(int pi = now; !OK && pi < prime.size(); pi++)
        {
            if( A[pi][Ni] == 1 )
            {
                OK = 1;

                for(int Nj = 0; Nj < N; Nj++)
                    swap(A[now][Nj], A[pi][Nj]);
            }
        }

        if( !OK ) continue;

        for(int pi = 0; pi < prime.size(); pi++)
        {
            if( pi == now || A[pi][Ni] == 0 ) continue;

            for(int Nj = 0; Nj < N; Nj++)
                A[pi][Nj] ^= A[now][Nj];
        }

        now++;
    }
}

int main()
{
    find_prime();

    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d", &N);

        for(int Ni = 0; Ni < N; Ni++)
            scanf("%lld", &num[Ni]);

        fill(A[0], A[499]+500, 0);

        for(int pi = 0; pi < prime.size(); pi++)
            for(int Ni = 0; Ni < N; Ni++)
            {
                long long x = num[Ni];
                int p = prime[pi];

                while( x%p == 0 )
                {
                    A[pi][Ni] ^= 1;
                    x /= p;
                }
            }

        process();

        int cnt = 0;

        for(int Ni = 0; Ni < N; Ni++)
        {
            for(int Nj = 0; Nj < N; Nj++)
            {
                if( A[Ni][Nj] )
                {
                    cnt++;
                    break;
                }
            }

        }


        cout<<(1LL<<N-cnt)-1<<endl;
    }
}

沒有留言:

張貼留言