Analiza

Primetimo da za svako ~k~ i svako ~N~ važi ~\lceil\frac{N}{k}\rceil \geq \frac{N}{k}~, iz čega sledi nejednakost ~\lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil \geq \frac{N}{p} +\frac{N}{q}+\frac{N}{r}~. U skladu sa ovim, razdvajamo problem na tri slučaja u zavisnosti od vrednosti ~p,q,r~:

Prvi slučaj: ~\frac{N}{p} +\frac{N}{q}+\frac{N}{r}>N~ ~\Leftrightarrow~ ~pq+pr+qr > pqr~

• Iz gornje nejednakosti imamo ~\lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil > N~, pa uslov tražen u zadatku ne može biti ispunjen ni za jedno ~N~, te je konačno rešenje ~0~, nezavisno od vrednosti ~L~ i ~R~.

Drugi slučaj: ~\frac{N}{p} +\frac{N}{q}+\frac{N}{r}=N~ ~\Leftrightarrow~ ~pq+pr+qr = pqr~

• U ovom slučaju imamo da je uslov tražen u zadatku ispunjen samo ako je ~\lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil = \frac{N}{p} +\frac{N}{q}+\frac{N}{r}~, što je moguće samo ako ~p|N~ i ~q|N~ i ~r|N~, što je ekvivalentno tome da ~d | N~, gde je ~d=NZS(p,q,r)~. Dakle, treba naći broj prirodnih brojeva deljivih sa ~d~ u intervalu ~[L,R]~. Ovo dobijamo računanjem broja takvih brojeva u ~[1,R]~ i oduzimanjem broja takvih brojeva u ~[1,L-1]~: ~\frac{R}{d} - \frac{L-1}{d}~.

Treći slučaj: ~\frac{N}{p} +\frac{N}{q}+\frac{N}{r}<N~ ~\Leftrightarrow~ ~pq+pr+qr < pqr~

• Poslednji slučaj je najsloženiji jer nas prvobitna nejednakost ne dovodi direktno do zaključka, tj. da li je podela moguća za neko ~N~ zavisi na netrivijalan način od deljivosti sa ~p,q,r~.
• Iako nas ograničenja za ~L~ i ~R~ odvraćaju od brute-force rešenja (prolazak kroz sve brojeve od ~L~ i ~R~ i provera da li je traženi izraz tačan), često je u ovakvim situacijama, kada je potrebno pronaći šablon, dobra ideja generisanje i posmatranje vrednosti koje brute-force proizvede. Ukoliko to ovde uradimo za npr. ~(p,q,r)=(2,3,7)~ (drugi podzadatak) i ~(L,R)=(1,300)~ možemo primetiti da je podela moguća za svako ~N \in [50, 300]~, iz čega prirodno pretpostavljamo da je moguća za svako ~N \geq 50~. U ovu pretpostavku se možemo dodatno ubediti povećavanjem ~R~.
• Ukoliko je ovo tačno za ~(p,q,r)=(2,3,7)~, tačno je i za svako drugo ~(p' \leq q' \leq r')~ koje spada u treći slučaj, jer mora da važi ~p'>p, q'>q, r'>r~ (proveriti!) pa je stoga (ako je naša pretpostavka tačna) za svako ~N > 50~: ~\lceil\frac{N}{p'}\rceil + \lceil\frac{N}{q'}\rceil + \lceil\frac{N}{r'}\rceil \leq \lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil \leq N~.
• Ovo nas dovodi do efikasnog rešenja za treći slučaj: za svako ~N < 50~ u ~[L,R]~ proverimo uslov "ručno", dok za ~N \geq 50~ pretpostavimo da sigurno važi. Ovo se ispostavlja kao tačno, a ukoliko želimo da budemo u potpunosti sigurni moguće je tvrdnju sličnu našoj pretpostavci i malo formanije dokazati (hint: posmatrati ponašanje izraza ~\lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil~ za ~nzs(p,q,r)|N~).