Zadanie
Petrovi pripadal jeho priateľ mimoriadne ustaraný, a tak mu nedalo, aby sa nespýtal aj na jeho rodinu. Feuer Sebastian si povzdychol a odpovedal:
„Vieš, my Bachovci sme boli vcelku známy rod, a tak sa nás nové opatrenia dotkli o to viac. Moje deti boli pridelené do továrne na epsilony, ja celé dni driem na nekonečnom poli. Skoro sa ani nevídame, domov nás nepustia, kým nesplníme kvóty.
No a tie kvóty sú strašné, každý deň musia moje deti vyprodukovať aspoň \(n=p^rq^s\) epsilonov, kde \(p,q\) sú navzájom rôzne prvočísla a \(r,s\) sú nezáporné celé čísla. Vieš si predstaviť, koľko potom existuje deliteľov čísla \(n^2\) neprevyšujúcich \(n\) a zároveň nedeliacich \(n\)? Ja nie, ale rád by som to vedel.“ Zistite to pre Sebastiana.
Zo zadania vieme, že \(p, q\) sú vzájomne rôzne prvočísla a že \(r, s \in \mathbb{Z}^{+}\). Číslo \(n\) je podľa zadania definované ako \(n = p^r q^s\), teda \(n^2 = (p^r q^s)^2 = p^{2r} q^{2s}\). Keďže chceme zistiť počet deliteľov \(n^2\) neprevyšujúcich a zároveň nedeliacich \(n\), poďme sa pozrieť na počty deliteľov čísel \(n^2\) a \(n\).
Ako zistíme počet deliteľov nejakého čísla? Nech číslo \(a\) má prvočíselný rozklad \(p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}\), kde \(p_1, p_2, \dots, p_k\) sú vzájomne rôzne prvočísla. Na to, aby bolo nejaké číslo \(d\) deliteľom čísla \(a\), musí platiť, že prvočíselný rozklad čísla \(d\) je nejaká časť prvočíselného rozkladu čísla \(a\). Musí teda obsahovať rovnaké prvočísla \(p_1, p_2, \dots, p_k\) ako prvočíselný rozklad čísla \(a\), no tieto prvočísla môžu mať iné exponenty, ktoré ale nemôžu byť väčšie ako exponenty v prvočíselnom rozklade \(a\). Teda keď chceme vytvoriť deliteľa čísla \(a\), tak pri každom prvočísle \(p\) z prvočíselného rozkladu vyberáme exponenty z množiny \(\left\{0, 1, \dots, m\right\}\), ktorých je \(m+1\). Počet deliteľov čísla \(a\) teda bude \((m_1 + 1) (m_2 + 1) \cdots (m_k + 1)\).
Koľko deliteľov teda má \(n\)? A koľko \(n^2\)? S použitím vyššie ukázaného vzorčeka vieme zistiť, že \(n\) má \((r + 1)(s + 1) = r s + r + s + 1\) deliteľov, zatiaľ čo \(n^2\) má \((2r + 1)(2s + 1) = 4rs + 2r + 2s + 1\) deliteľov. Nech \(d \in \mathbb{Z}^+\) je nejaký deliteľ \(n^2\), ktorý neprevyšuje \(n\). Potom vieme, že podiel \(\frac{n^2}{d}\) určite nie je menší ako \(n\), teda \(\frac{n^2}{d} \geq n\). Každý deliteľ \(n^2\), ktorý je menší alebo rovný ako \(n\), má svoj „opak“, teda deliteľa väčšieho alebo rovného \(n\). Polovica deliteľov \(n^2\) bude menšia alebo rovná \(n\), čo je \(2rs + r + s + 1\) deliteľov (\(n^2\) má \(n\) ako „zdvojeného deliteľa“). Taktiež však vieme, že každý deliteľ \(n\) je aj deliteľom \(n^2\) a zároveň žiaden z deliteľov čísla \(n\) ho určite neprevyšuje. Počet deliteľov čísla \(n^2\), ktoré neprevyšujú číslo \(n\) a ani nie sú jeho deliteľmi, je teda \((2rs + r + s + 1) - (rs + r + s + 1) = rs\).
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ť.