SPOJ Twosqrs

#include <cstdio>
#include <cmath>
#include <cstring>

typedef long long tint;

const int SIZE = 1000001;
tint primos[80000],factor[1024],mult[1024];
int P,F;

char _criba[SIZE];

void criba(){
    P = 0;
    memset(_criba,0,sizeof(_criba));

    for(int k = 2; k < SIZE; k++){
        if(!_criba[k]){
            primos[P++] = k;
            for(int j = 2*k; j < SIZE; j+=k)
                _criba[j] = 1;
        }
    }
}

void factorear(tint x){
    bool once,found = false;

    for(int i = 0; i < P && primos[i]*primos[i] <= x; i++){
        once = false;
        while(x % primos[i] == 0){
            found = true;
            if(!once){
                factor[F] = primos[i], mult[F++] = 0;
                once = true;
            }

            mult[F-1]++;
            x = x/primos[i];
        }
    }

    if(!found) factor[F] = x, mult[F++] = 1; else factorear(x);
}

int main(){
#ifdef ACM
    freopen("test.in","r",stdin);
#endif
    criba();

    int t; scanf("%d\n", &t);
    tint val;

    while(t-- > 0){
        scanf("%lld\n",&val);

        factor[0] = 1, F = 0;

        factorear(val);
        bool ok = true;

        for(int i = 0; i < F; i++)
            ok = ok && !(factor[i] % 4 == 3 && mult[i] % 2 == 1);

        if(ok) printf("Yes\n"); else printf("No\n");
    }
    return 0;
}