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})\).
Primer 3.2.4. 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})\).
long long dopunaDoPunogKvadrata(long long n) {
// dopuna
long long m = 1;
// rastavljamo broj n na proste cinioce
// kandidat za prost cinilac
long long p = 2;
while (p * p <= n) {
// racunamo visestrukost cinioca p
int k = 0;
while (n % p == 0) {
n /= p;
k++;
}
// ako se cinilac p javlja neparan broj puta tada se on mora
// javiti u dopuni m
if (k % 2 != 0)
m *= p;
// prelazimo na sledeceg kandidata
p++;
}
// n se sveo na svoj najveci prost cinilac
if (n > 1)
// i on mora da ucestvuje u dopuni
m *= n;
return m;
}#include <iostream>
using namespace std;
long long dopunaDoPunogKvadrata(long long n) {
// dopuna
long long m = 1;
// rastavljamo broj n na proste cinioce
// kandidat za prost cinilac
long long p = 2;
while (p * p <= n) {
// racunamo visestrukost cinioca p
int k = 0;
while (n % p == 0) {
n /= p;
k++;
}
// ako se cinilac p javlja neparan broj puta tada se on mora
// javiti u dopuni m
if (k % 2 != 0)
m *= p;
// prelazimo na sledeceg kandidata
p++;
}
// n se sveo na svoj najveci prost cinilac
if (n > 1)
// i on mora da ucestvuje u dopuni
m *= n;
return m;
}
int main() {
long long n;
cin >> n;
cout << dopunaDoPunogKvadrata(n) << endl;
return 0;
}