Допуна до пуног квадрата

Напиши програм који за унети природни број \(n\) одређује најмањи број \(m\) такав да је \(n \cdot m\) потпун квадрат.

Опис улаза

Са стандардног улаза се уноси природни број \(n\) (\(1 \leq n \leq 2 \cdot 10^{12}\)).

Опис излаза

На стандардни излаз исписати тражени број \(m\).

Пример

Улаз

104

Излаз

26

Решење

Најмањи број којим се \(n\) множи да би се добио потпун квадрат мора бити делилац броја \(n\) (он мора да буде производ простих фактора броја \(n\) који се јављају са непарном вишеструкошћу). Зато можемо испитати све делиоце броја \(n\) (линеарном претрагом) и проверити који је први који када се помножи са \(n\) даје потпун квадрат. Проверу да ли је број потпун квадрат можемо вршити уз помоћ функције (реалног) кореновања (додуше, то може некада довести до грешака услед непрецизности у запису реалних бројева).

Пошто се делиоци јављају увек у пару (ако је број \(d\) делилац броја \(n\), онда је делилац и број \(n/d\)), претрагу можемо вршити само до вредности \(\sqrt{n}\).

Najmanji broj kojim se \(n\) množi da bi se dobio potpun kvadrat mora biti delilac broja \(n\) (on mora da bude proizvod prostih faktora broja \(n\) koji se javljaju sa neparnom višestrukošću). Zato možemo ispitati sve delioce broja \(n\) (linearnom pretragom) i proveriti koji je prvi koji kada se pomnoži sa \(n\) daje potpun kvadrat. Proveru da li je broj potpun kvadrat možemo vršiti uz pomoć funkcije (realnog) korenovanja (doduše, to može nekada dovesti do grešaka usled nepreciznosti u zapisu realnih brojeva).

Pošto se delioci javljaju uvek u paru (ako je broj \(d\) delilac broja \(n\), onda je delilac i broj \(n/d\)), pretragu možemo vršiti samo do vrednosti \(\sqrt{n}\).

Ako je broj \(d \leq \sqrt{n}\) prvi koji zadovoljava uslov, on je najmanji takav i pretraga se može prekinuti. Sa druge strane, kada broj \(n / d\) zadovolji uslov, samo to registrujemo i nastavljamo pretragu, jer ne znamo da je on najmanji takav.

Osim što može biti donekle neefikasna, osnovni problem sa ovakvom implementacijom je to što broj \(n\) i njegovi delioci mogu biti 64-bitni brojevi, pa se njihov proizvod ne može predstaviti ispravno 64-bitnim brojem, tako da ovaj pristup može da da garantovano ispravne rezultate samo ako je \(n \leq 10^9\).

Složenost ovog pristupa je \(O(\sqrt{n})\).

#include <iostream>
#include <cmath>

using namespace std;

bool is_square(long long k) 
{
    long long sqrt_k = (long long) sqrt(k);

    return sqrt_k * sqrt_k == k;
}

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

    long long min = 1;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            if (is_square(n * d)) {
                min = d;
                break;
            }
            if (is_square(n * (n / d))) {
                min = n / d;
            }
        }
    }

    cout << min << endl;

    return 0;
}

Razmotrimo broj \(234\). On se može rastaviti na proste činioce kao \(2 \cdot 3 \cdot 3 \cdot 13\). Da bi ovaj broj bio potpun kvadrat potrebno je da se svaki činilac ponovi paran broj puta i zato je tražena dopuna \(2 \cdot 13\). Zaista, množenjem sa \(2\cdot 13 = 26\) dobija se broj \(2^2 \cdot 3^2 \cdot 13^2\) koji je kvadrat broja \(2 \cdot 3 \cdot 13 = 78\).

Kada se pun kvadrat rastavi na proste činioce, svaki činilac se javlja paran broj puta. Ako je broj \(n = p_1^{k_1}\cdot \ldots \cdot p_m^{k_m}\), tada je tražena dopuna jednaka proizvodu onih činilaca \(p_i\) za koji je višestrukost \(k_i\) neparan broj. Dakle, zadatak se jednostavno rešava primenom algoritma rastavljanja na proste činioce.

Izdvajamo činilac po činilac broja i za svaki od njih brojimo višestrukost (tako što svaki put kada podelimo broj \(n\) sa nekim prostim činiocem \(p\) uvećamo vrednost brojača \(k\)). Kada utvrdimo da neki činilac ima neparnu višestrukost, tada njime množimo trenutnu vrednost broja \(m\) (koju inicijalizujemo na 1).

Primetimo da nema potrebe da izračunavamo proizvod brojeva \(n\) i \(m\), pa je ispravno sve vreme koristiti 64-bitni tip podataka (koji je dovoljan za zapis brojeva \(n\) i \(m\), ali ne i njihovog proizvoda).

Složenost ovog algoritma odgovara složenosti rastavljanja na proste činioce, a to je \(O(\sqrt{n})\).

#include <iostream>

using namespace std;

long long dopunaDoPunogKvadrata(long long n) 
{
    long long m = 1;

    long long p = 2;
    while (p * p <= n) {
        int k = 0;
        while (n % p == 0) {
            n /= p;
            k++;
        }
        if (k % 2 != 0)
            m *= p;

        p++;
    }

    if (n > 1)
        m *= n;

    return m;
}

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

    cout << dopunaDoPunogKvadrata(n) << endl;

    return 0;
}

Ако је број \(d \leq \sqrt{n}\) први који задовољава услов, он је најмањи такав и претрага се може прекинути. Са друге стране, када број \(n / d\) задовољи услов, само то региструјемо и настављамо претрагу, јер не знамо да је он најмањи такав.

Осим што може бити донекле неефикасна, основни проблем са оваквом имплементацијом је то што број \(n\) и његови делиоци могу бити 64-битни бројеви, па се њихов производ не може представити исправно 64-битним бројем, тако да овај приступ може да да гарантовано исправне резултате само ако је \(n \leq 10^9\).

Сложеност овог приступа је \(O(\sqrt{n})\).

Размотримо број \(234\). Он се може раставити на просте чиниоце као \(2 \cdot 3 \cdot 3 \cdot 13\). Да би овај број био потпун квадрат потребно је да се сваки чинилац понови паран број пута и зато је тражена допуна \(2 \cdot 13\). Заиста, множењем са \(2\cdot 13 = 26\) добија се број \(2^2 \cdot 3^2 \cdot 13^2\) који је квадрат броја \(2 \cdot 3 \cdot 13 = 78\).

Када се пун квадрат растави на просте чиниоце, сваки чинилац се јавља паран број пута. Ако је број \(n = p_1^{k_1}\cdot \ldots \cdot p_m^{k_m}\), тада је тражена допуна једнака производу оних чинилаца \(p_i\) за који је вишеструкост \(k_i\) непаран број. Дакле, задатак се једноставно решава применом алгоритма растављања на просте чиниоце.

Издвајамо чинилац по чинилац броја и за сваки од њих бројимо вишеструкост (тако што сваки пут када поделимо број \(n\) са неким простим чиниоцем \(p\) увећамо вредност бројача \(k\)). Када утврдимо да неки чинилац има непарну вишеструкост, тада њиме множимо тренутну вредност броја \(m\) (коју иницијализујемо на 1).

Приметимо да нема потребе да израчунавамо производ бројева \(n\) и \(m\), па је исправно све време користити 64-битни тип података (који је довољан за запис бројева \(n\) и \(m\), али не и њиховог производа).

Сложеност овог алгоритма одговара сложености растављања на просте чиниоце, а то је \(O(\sqrt{n})\).

#include <iostream>

using namespace std;

long long dopunaDoPunogKvadrata(long long n) 
{
    long long m = 1;

    long long p = 2;
    while (p * p <= n) {
        int k = 0;
        while (n % p == 0) {
            n /= p;
            k++;
        }
        if (k % 2 != 0)
            m *= p;

        p++;
    }

    if (n > 1)
        m *= n;

    return m;
}

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

    cout << dopunaDoPunogKvadrata(n) << endl;

    return 0;
}