| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_04_09 - Silnia |
Silnia
Niech k oznacza iloczyn wszystkich liczb pierwszych od 2 do z . Zadanie polega na znalezieniu
maksymalnego p, takiego ze równanie:
n! mod k^p = 0;
jest prawdziwe.
np. dla n=10 i z=5 :
10!=3628800
iloczyn wszystkich liczb pierwszych od 2 do 5 = 2*3*5=30;
10!= 30^2 * 4032
czyli 10! mod 30^2 = 0;
p=2;
Niech k oznacza iloczyn wszystkich liczb pierwszych od 2 do z . Zadanie polega na znalezieniu maksymalnego p, takiego ze równanie:
n! mod kp ≡ 0
jest prawdziwe.
Wyjaśnienie
np. dla n=10 i z=5
10!=3628800
iloczyn wszystkich liczb pierwszych od 2 do 5 wynosi
2⋅3⋅5 = 30
10! = 302 ⋅ 4032
czyli
10! mod 302 ≡ 0
gdzie p=2.
Wejście
W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (t < 10001).
Specyfikacja każdego z t wierszy:
każdy wiersz składa się z dwóch liczb całkowitych n i z takich, że 1 < z ≤ 107, przy czym z jest zawsze liczbą pierwszą oraz 1 ≤ n ≤ 109.
Wyjście
Dla każdego zestawu testowego szukane p.
Przykład
Wejście:
1
10 5
Wyjście:
2
| Dodane przez: | Marcin Kasprowicz |
| Data dodania: | 2015-07-15 |
| Limit czasu wykonania programu: | 1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU JS-MONKEY |