Zadanie
Je pondelňajšie ráno a Kubo sa vyvaľuje na gauči v T21. Aby zvládol náročný týždeň sedenia na prednáškach, v batohu si so sebou dovliekol hromadu čokolád. V momente, ako začal jednu rozbaľovať, dvere do T2 sa otvorili a zjavili sa v nich Vlejd s Baškou. Sotva zračili fialový obal, div si neoslintali svoje krásne nové KSP tričká.
Kubovi bolo teda hneď jasné, že sa bude musieť o čokolády deliť. Kubo je krásny, spravodlivý a prajný, preto sa chce deliť rovnomerne. Rýchlo v hlave prerátal, koľko dielikov treba každému z nich troch ulomiť, no skôr ako stihol čokoládu prerozdeliť, dvere sa rozleteli znova a vošla Šandyna s Jarom. Celý proces slintania a prerátavania sa zopakoval, no to sa už do T2-ky tlačil Adam s Dendou. Kubo, vidiac tento nemilý trend, začal premýšľať.
Koľko najviac vedúcich môže ešte do T2 prísť po dvojiciach tak, aby im mohol (vrátane seba) spravodlivo rozdeliť čokoládu?
Úloha
Keďže vedúci prichádzajú do T2 po dvojiciach, spolu s Kubom ich bude vždy nepárny počet. Každá z Kubových čokolád má nejaký počet dielikov (označme ho \(n\)), ktoré by chcel (teda, už musí :) ) rovnomerne prerozdeliť spravodlivo medzi seba a zvyšných vedúcich. Zaujíma ho najväčší možný počet vedúcich, pre ktorý sa čokoláda ešte dá rozdeliť. A vy mu s tým máte pomôcť.
Formát vstupu
Na prvom riadku sa nachádza číslo \(q\) – počet čokolád, ktoré má Kubo v batohu. Nasleduje \(q\) riadkov, pričom \(i\)-ty z nich obsahuje číslo \(n_i\) – počet dielikov \(i\)-tej čokolády. Pre jednotlivé testovacie sady sú horné limity pre \(q\) a \(n_i\) dané nasledujúcou tabuľkou:
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(1 \leq n_i \leq\) | \(2^{16}\) | \(2^{32}\) | \(2^{60}\) | \(2^{60}\) |
\(1 \leq q \leq\) | \(100\) | \(500\) | \(1\,000\) | \(10\,000\) |
(Nezabudnite použit 64bitové premenné. V C++ long long, v Pascale Int64, v Jave long)
Formát výstupu
Pre každú čokoládu vypíšte jeden riadok obsahujúci najväčší (nepárny) počet vedúcich, medzi ktorých sa dá čokoláda rozdeliť rovnomerne.
Príklady
Input:
3
24
60
1
Output:
3
15
1
Čokoládu s 24 dielikmi vieme rovnomerne rozdeliť medzi troch vedúcich (každému dáme 8 dielikov). Čokoládu s 60 dielikmi vieme rozdeliť medzi pätnástich (každému dáme 4 dieliky). Čokoláda s jedným dielikom sa nedá deliť, takže ju Kubo musí zjesť, keď bude niekde sám.
T2 je KSP-ácka miestnosť na matfyze↩
Pre zadaný počet dielikov čokolády \(n\) chceme vedieť, koľkým najviac vedúcim ich vieme spravodlivo rozdeliť, ak je vedúcich nepárne veľa. V preklade to znamená, že hľadáme najväčšie nepárne číslo \(k\), ktoré delí \(n\) bezo zvyšku.
Úplne najjednoduchšie riešenie môže fungovať tak, že postupne budeme cyklom prechádzať čísla \(1 \dots n\) a pre každé otestujeme, či je nepárne a zároveň deliteľom \(n\). Ak také nájdeme, uložíme si ho, a po skončení cyklu tak dostaneme správnu odpoveď. Takéto riešenie hrubou silou má pre jedno \(n\) časovú zložitosť \(O(n)\), pre \(q\) požiadavok \(O(n \cdot q)\) a mohli ste zaň dostať maximálne jeden bod.
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
long long n,q;
scanf("%lld", &q);
for (long long i = 0; i < q; i++){
scanf("%lld", &n);
long long m = 1;
for (int k = 2; k <= n + 1; k++){
if (n % k == 0 && k % 2 == 1){
m = k;
}
}
printf("%lld\n", m);
}
}
Predošlé riešenie vieme vylepšiť tak, že budeme deliteľe skúšať nie po \(n\) ale iba \(\sqrt{n}\). Ak by totiž \(n\) malo deliteľ \(d\) väčší ako \(\sqrt{n}\) potom nutne \(n \div d < \sqrt{n}\). Prejdeme teda \(1 \dots \sqrt{n}\) a pre každé číslo \(k\) z tohto intervalu sa pozrieme, či delí \(n\). Ak áno, pozrieme sa, či \(k\) alebo \(n \div k\) je nepárne a ak je, aktualizujeme jeho hodnotou doterajšie nájdené maximum. Toto riešenie má celkovú časovú zložitosť \(O(\sqrt{n} \cdot q)\) a na testovači získalo maximálne dva body (aj to len v rýchlych jazykoch).
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
long long n,q;
scanf("%lld", &q);
for (long long i = 0; i < q; i++){
scanf("%lld", &n);
long long m = 1;
for (long long j = 1; j < (long long)ceil(sqrt(n)); j++){
if (n % j == 0){
if (j % 2 == 1) m = max(m,j);
if ((n / j) % 2 == 1) m = max(m,j)
}
}
printf("%lld\n", m);
}
}
Dostávame sa ku vzorovému riešeniu. Zamyslime sa, ako vieme efektívne nájsť všetky deliteľe čísla, alebo aspoň ich počet. Odpoveďou je rozklad na prvočísla, s ktorým ste sa už určite stretli. Každý deliteľ čísla \(n\) je súčinom niekoľkých (možno aj nula, možno aj všetkých) prvočísel z prvočíselného rozkladu \(n\). Aby sme dostali nepárny súčin, musíme násobiť iba nepárne čísla. Najväčší nepárny deliteľ čísla \(n\) teda bude súčin všetkých nepárnych prvočísel z prvočíselného rozkladu \(n\)1.
To znamená, že z rozkladu stačí eliminovať všetky dvojky, keďže dvojka je jediné párne prvočíslo. V praxi nám teda stačí číslo \(n\) deliť dvojkou kým to ide a akonáhle to nejde, dostali sme náš hľadaný najväčší nepárny deliteľ.
Náš algoritmus urobí pre každé \(n\) iba toľko krokov, koľkokrát je \(n\) deliteľné dvojkou. V najhoršom prípade je \(n\) mocninou dvojky a algoritmus by sa delením dostal až ku jednotke. Urobil by teda logaritmicky2 veľa krokov od veľkosti \(n\) a teda časová zložitosť tohto riešenia je \(O(\log_2 n \cdot q)\). Toto riešenie už získa po otestovaní plný počet bodov.
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
long long n,q;
scanf("%lld", &q);
for (long long i = 0; i < q; i++){
scanf("%lld", &n);
while (n % 2 == 0) n /= 2;
printf("%lld\n", n);
}
}
Pre matematických detailistov: ak obsahuje prvočíselný rozklad čísla \(n\) nejaké prvočíslo vo vyššej mocnine, chápeme to tak, že obsahuje viac rovnakých prvočísel.↩
Logaritmus čísla \(n\) so základom \(a\) nám hovorí, na koľkú treba umocniť \(a\), aby sme dostali \(n\). Napríklad \(\log_2 16 = 4\) a \(\log_3 27 = 3\)↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.