2. Riadny strach vzorové riešenie

20 15

4 5

Čo vlastne hľadáme

Chceli by sme zistiť pre aké veľkosti skupiniek od \(1\) po \(n\) budú Krtko a Jerry zavolaní spolu. To vieme však vypočítať ako \(n\) mínus počet veľkostí skupiniek, pre ktoré budú Krtko a Jerry zavolaní oddelene, teda keď budú patriť do dvoch rôznych po sebe idúcich skupiniek.

A čo musí veľkosť skupinky spĺňať, aby Krtka a Jerry rozdelila? No čísla \(r-1\) a \(r\) musia patriť do dvoch rôznych skupiniek, teda ak \(r-1\) patrí do skupinky číslo \(k\), tak \(r\) patrí do skupinky číslo \(k+1\). Ak tieto skupinky majú veľkosť \(x\), tak potom bolo v prvých \(k\) skupinkách dokopy \(kx = r-1\) študentov. Aby toto nastalo, musí byť \(r-1\) násobkom veľkosti skupinky \(x\), inými slovami \(x\) musí byť deliteľom \(r-1\). Keďže každý deliteľ \(r-1\) označujúci veľkost skupinky dosiahne rozdelenie Krta a Jerry, celá úloha je vlastne len ‘vypíš (\(n\) mínus počet deliteľov \(r-1\)) deleno \(n\) v základnom tvare’.

Všetky možnosti

Každý celočíselný deliteľ \(r-1\) leží medzi \(1\) a \(r-1\), vrátane – môžeme teda všetky vyskúšať.

Prejdeme for cyklom čísla od \(1\) po \(r-1\), a ak je zvyšok po delení¹ rovný nule, pripočítame k odpovedi jedna.

Nakoniec chceme vypísať zlomok \(\frac{n-odpoved}{n}\) v základnom tvare, teda tak aby \(n-odpoved\) a \(n\) nemali spoločné delitele okrem \(1\). Môžeme jednoducho prejsť všetky čísla od \(1\) po \(n-odpoved\), a všetkými ktoré delia aj \(n-odpoved\) aj \(n\) ich predelíme dokým ich nedelia.

Keďže v cykle prechádzame čísla od \(1\) po \(r-1\), čo je najviac \(n\), a vždy vykonáme niekoľko konštantných operácií, toto nám zaberie \(O(n)\) času. V druhom cykle tiež určite neprejdeme viac ako \(n\) čísel, čiže celková časová zložitosť je \(O(n)\).

Stačí si nám pritom pamätať len konštantne veľa premenných, čiže pamäťová zložitosť je \(O(1)\).

#include<iostream>

using namespace std;

int main()
{
	long long n, r;
	cin >> n >> r;
	
	long long counter = 0;	
	
	for (long long i=1; i<=r-1; ++i)
	{
		if ((r-1)%i == 0) counter++;
	}
	
	long long citatel = n-counter;
	long long menovatel = n;

	for (long long i=2; i<=citatel;i++)
	{
		while(citatel%i == 0 && menovatel%i == 0)
		{
			citatel = citatel/i;
			menovatel = menovatel/i;
		}
	}
	cout << citatel << " " << menovatel << endl;	
}

Vzorové riešenie

Ako vieme nájsť počet deliteľov efektívnejšie?

Použijeme pozorovanie ktoré sa často v úlohách o deliteľoch a prvočíslach používajú: ak \(a \cdot b = x\), tak aspoň jedno z \(a,\ b \leq \sqrt{n}\).

Každý deliteľ väčší-rovný \(\sqrt{n}\) má svojho spoločníka ktorý je menší-rovný ako \(\sqrt{n}\). Stačí nám teda hľadať delitele po odmocninu z \(r-1\), a za každý nájdený pripočítať dva, ledaže by práve platilo \(x^2 = r-1\), kde sa deliteľ opakuje a my ho chceme zarátať len raz.

Skrátime teda náš for cyklus a trochu ho prepíšeme, a máme riešenie v \(O(\sqrt{n})\).

Na nájdenie zlomku v základnom tvare použijeme Euklidov algoritmus na nájdenie najväčšieho spoločného deliteľa čitateľa a menovateľa, a predelíme ich ním. Euklidov algoritmus zbehne v \(O(logn)\), číže celé riešenie nám pobeží v \(O(\sqrt{n})\).

Pamäťová zložitosť sa nezmenila – \(O(1)\).

#include <iostream>

using namespace std;

long long GCD(long long a, long long b)
{
    	if (a>b) swap(a,b);
    	if (a==0) return b;
    	return GCD(b%a, a);
}

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

   	long long counter = 0;
	
	for (long long i = 1; i*i <= r-1; ++i)
	{
    	if ((r-1)%i == 0) counter += 2;
	if (i*i == r-1) counter--;
	}

	long long cit = n-counter;
	cout << cit/GCD(cit, n)<< " " << n/GCD(cit, n)<< endl;

	return 0;
}