Proizvodi potpuni kvadrati

Na tabli je zapisan broj 1. Imamo niz \(a\) od \(n\) prirodnih brojeva i u \(i\)-tom koraku (\(1 \leq i \leq n\)) brišemo trenutni broj na tabli i umesto njega pišemo proizvod njega i broja \(a_i\). Posle svakog koraka odrediti da li je trenutni broj na tabli potpun kvadrat.

Opis ulaza

U prvom redu standardnog ulaza nalazi se prirodan broj \(n\) (\(1 \leq n \leq 10000\)) koji predstavlja dužinu niza \(a\). U narednom redu nalazi se \(n\) prirodnih brojeva (između 1 i milijardu) razdvojenih razmakom - to su elementi niza \(a\) u redosledu kojim množe trenutni broj na tabli.

Opis izlaza

Za svaki element niza \(a\), u redosledu kao na ulazu, ispisati da ukoliko je njegov proizvod sa trenutnim brojem na tabli potpun kvadrat a inače ispisati ne.

Primer

Ulaz

Izlaz

Rešenje

Faktorizacija izračunavanjem delilaca

S obzirom na to da ne možemo da predstavimo proizvod korišćenjem celobrojnog tipa (čak ni pomoću 64-bita), umesto samog broja, čuvaćemo spisak njegovih prostih činilaca. Da bi broj bio potpun kvadrat, svaki prost činilac treba da se javlja paran broj puta. Možemo smatrati da se svaka dva identična prosta činioca “skraćuju” tj. ne utiču na to da li je broj potpun kvadrat ili nije. Zato umesto svih prostih činilaca proizvoda možemo čuvati samo one koji su preostali nakon takvog skraćivanja (to su nedostajući činioci i svaki od njih treba da se javi neparan broj puta u narednim množenjima da bi broj postao potpun kvadrat). Te činioce možemo pamtiti u obliku skupa (u jeziku C++ možemo koristiti set ili unordered_set). (u jeziku C# možemo koristiti SortedSet ili HashSet).

Kada broj rastavimo na proste činioce (algoritmom opisanim u zadatku [rastavljanje_na_proste_cinioce]), analiziramo jedan po jedan činilac i one koji trenutno nisu u skupu dodajemo u skup, a one koji jesu, izbacujemo iz skupa. Broj je potpun kvadrat ako i samo ako je skup prazan nakon obrade svih njegovih činilaca.

Ilustrujmo na kraju rad ovog algoritma na primeru.

i   ai     cinioci            skup     kvadrat
0   2      2                  {2}      ne
1   3      3                  {2, 3}   ne
2   6      2, 3               {}       da
3   15     3, 5               {3, 5}   ne
4   35     5, 7               {3, 7}   ne
5   21     3, 7               {}       da
6   64     2, 2, 2, 2, 2, 2   {}       da

Neka je \(K\) maksimum niza. Svaki od \(n\) brojeva rastavljamo na proste činioce, za šta nam je ukupno potrebno vreme \(O(n \sqrt{K})\). Kako je \(K \leq 10^9\), svaki element niza može da ima najviše tridesetak prostih činilaca (\(2^{30}\approx 10^9\)). U opštem slučaju, broj prostih činilaca svakog elementa je \(O(\log{K})\), pa je ukupan broj dodavanja u skup i izbacivanja iz skupa \(O(n \log{K})\). Pošto će skup u svakom trenutku imati ne više od tridesetak elemenata, složenost ubacivanja i brisanja iz takvog skupa se može smatrati konstantnom. Ukupna složenost je, dakle, određena faktorizacijom, tj. jednaka je \(O(n \sqrt{K})\).

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

vector<int> get_factors(int n) 
{
    vector<int> factors;

    int d = 2;
    while (d * d <= n) {
        while (n % d == 0) {
            factors.push_back(d);
            n /= d;
        }
        d++;
    }

    if (n > 1) {
        factors.push_back(n);
    }

    return factors;
}

int main() 
{
    int n; cin >> n;

    unordered_set<int> missing_factors;

    for (int i = 0; i < n; i++) {
        int x; cin >> x;

        vector<int> factors = get_factors(x);

        for (int p : factors) {
            auto it = missing_factors.find(p);
            if (it != missing_factors.end()) {
                missing_factors.erase(it);
            } else {
                missing_factors.insert(p);
            }
        }

        cout << (missing_factors.empty() ? "da" : "ne") << '\n';
    }

    return 0;
}

Primena Eratostenovog sita

Zadatak može da se reši efikasnije pomoću Eratostenovog sita. Pošto je gornje ograničenje elemenata niza \(K=10^9\), dovoljno je pomoću sita naći proste brojeve do \(\left\lceil{\sqrt{10^9}}\right\rceil\) i smestiti ih u niz prosti. Faktorizaciju vršimo slično kao i bez sita, s tim da ne pokušavamo deljenje svakim prirodnim brojem, nego samo elementima niza prosti. Kao i kada faktorišemo bez sita, traženje delilaca prekidamo kada kvadrat tekućeg kandidata za delilac postane veći od broja koji faktorišemo.

Za formiranje sita potrebno vreme je \(O(\sqrt{K})\). Nakon toga, vreme faktorisanja svakog broja \(x\) srazmerno je broju prostih brojeva manjih od \(\sqrt{x}\), a to je \(O(\frac{\sqrt{K}}{\log{K}})\). Prema tome, ukupno vreme je \(O(n \frac{\sqrt{K}}{\log{K}})\).

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>

typedef long long LL;

using namespace std;

unordered_set<LL> missing_factors;

vector<int> get_primes(const int n)
{
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;

    is_prime[0] = false;
    is_prime[1] = false;

    int i = 2;
    while (i * i <= n + 11) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
        i++;
    }

    for (int j = i; j <= n; j++) {
        if (is_prime[j]) {
            primes.push_back(j);
        }
    }

    return primes;
}

void update_missing(LL c) 
{
    auto it = missing_factors.find(c);
    if (it != missing_factors.end())
        missing_factors.erase(it);
    else
        missing_factors.insert(c);
}

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;

    int K = 1e9; // ogranicenje iz teksta zadatka

    auto primes = get_primes((int) ceil(sqrt(K)));

    for (int i = 0; i < n; i++) {
        LL x;
        cin >> x;
        for (auto p : primes) {
            while (x % p == 0) {
                x /= p;
                update_missing(p);
            }
            if (x < p * p) {
                break; 
            }
        }
        if (x > 1) {
            update_missing(x);
        }

        cout << (missing_factors.empty() ? "da" : "ne") << '\n';
    }
    return 0;
}