1. Črieda pažravých vedúcich vzorové riešenie

3
24
60
1

3
15
1

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\)¹.

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 logaritmicky² 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);
	}
}