Omówienie zadania Siłownia dla początkujących (I etap XXXIII OI, tura zdalna)

Dla danej liczby \(n\) z zakresu od 1 do \(10^9\) chcemy sprawdzić, czy istnieją całkowite dodatnie współczynniki \(a,b\) takie że \(3a+8b=n\).

Intuicja w rozwiązaniu jest taka, że jeśli \(n\) jest dostatecznie duże, to jakoś uda się przedstawić \(n\) w żądany sposób, jako że mamy wtedy dużą swobodę doboru współczynników. W tym zadaniu wystarczy, jeśli \(n \ge 16\). Faktycznie, liczby \(n,n-8,n-16\) mają różne reszty z dzielenia przez 3 (ponieważ \(8 \bmod 3 = 2\) i \(16 \bmod 3 = 1\)), więc jeśli \(n \ge 16\), to wszystkie one będą nieujemne i któraś z nich będzie podzielna przez 3. Jeśli np. tą liczbą jest \(n-16\), to mamy \(n=3a+8 \cdot 2\) dla \(a=(n-16)/3\).

Wiemy już, jak odpowiadać w przypadku \(n \ge 16\). A co jeśli \(n \le 15\)? Możemy np. sprawdzić wszystkie kombinacje \(a,b \in \{0,\ldots,5\}\) i zobaczyć, czy przy którejś z nich mamy \(3a+8b=n\).

Ostatecznie rozwiązanie działa w czasie stałym, niezależnym od \(n\).

W ogólności, dla dowolnych względnie pierwszych liczb całkowitych dodatnich \(p,q\), każdą liczbę całkowitą \(n\) taką że \(n > pq-p-q\) można przedstawić jako \(n=ap+bq\) dla pewnych liczb całkowitych nieujemnych \(a,b\). Jest to tzw. problem Frobeniusa. (Powyższy dowód uogólnia się do słabszego ograniczenia \(n \ge pq-p\).)