Zadanie
Krtko a Jerry sa idú zapísať na ústnu skúšku z analýzy. Keďže analýza je najväčší strašiak matfyzákov, chceli by sa na skúške navzájom podporovať svojou prítomnosťou. Vedia, že profesor vždy volá študentov na ústnu skúšku po skupinkách. Najväčšia šanca, že budú v jednej skupinke je, ak sa zapíšu hneď po sebe. Na skúšku sa však musia poctivo pripravovať, preto nemajú čas zisťovať, na ktoré miesto sa majú zapísať aby išli s čo najväčšou pravdepodobnosťou spolu. Pomôžete im?
Úloha
Na skúšku je voľných \(n\) miest. Zistite, aká je pravdepodobnosť, že Krtko a Jerry pôjdu spolu na skúšku ak sa Jerry zapíše na \(r\)-tú pozíciu a Krtko hneď pred ňu. Profesor si vždy pred skúškou náhodne zvolí \(x\) – veľkosť skupiniek po ktorých bude študentov volať dnu, pričom platí, že \(1 \leq x \leq n\). Každá veľkosť skupinky od \(1\) po \(n\) je rovnako pravdepodobná.
Formát vstupu
Na vstupe sa nachádza jeden riadok a v ňom dve čísla: \(n\) - počet ľudí zapísaných na danú skúšku a \(r\) - poradie Jerry, pričom platí \((2 \leq r \leq n \leq 10^{12})\). Pozor, v jazykoch podobných C++ vám nemusí na uloženie \(n\) a \(r\) stačiť klasický typ int
. Riešením(v C++) je napr. použiť typ long long
.
V testovacích sadách platia pre \(n\) a \(r\) nasledovné obmedzenia zhora:
Sada | 1 a 2 | 3 | 4 | 5 | 6 až 8 |
---|---|---|---|---|---|
\(n,r \leq\) | \(10\,000\) | \(100\,000\) | \(150\,000\,000\) | \(250\,000\,000\) | \(10^{12}\) |
Formát výstupu
Vypíšte dve medzerou oddelené čísla \(p\) a \(q\) kde \(p\) je čitateľ a \(q\) menovateľ zlomku, ktorý vyjadruje pravdepodobnosť s akou pôjdu Krtko s Jerry odpovedať v jednej skupinke. Zlomok naviac vypíšte v základnom tvare.
Príklad
Input:
20 15
Output:
4 5
Na skúšku je zapísaných 20 ľudí pričom Krtko je v poradí 14. a Jerry 15. Krtko a Jerry budú spolu v skupinke ak bude profesor volať študentov po skupinkách veľkosti 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19 alebo 20. Celkovo profesor môže vymyslieť 20 rôznych veľkostí skupiniek (1-20), preto je pravdepodobnosť, že pôjdu spolu 16/20, teda v základnom tvare 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í1 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;
}
Vo viacerých jazykoch je operátor na zvyšok po delení
%
↩
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ť.