|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #24Ended |
A - Pelea de Primos I
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Ocurre una catástrofe en Numberland, el número primo p esta celoso del número primo q. El cree que que hay mas números entre a y b inclusive que son divisibles por una mayor potencia de q que de p. Debemos ayudar a p a liberarse de este sentimiento. Sea a(n,x) el máximo k tal que n es divisible por x^k. Digamos que el numero n es p-dominante sobre q si a(n,p) > a(n,q). Encuentre cuantos numeros entre a y b inclusive son p-dominante sobre q.
Input
La primera y única linea de la entrada contiene a, b, p y q ;p 6= q; p y q son primos.
• En el subproblema I se cumple (1 ≤ a ≤ b ≤ 10^7);2 ≤ p,q ≤ 10^3
• En el subproblema II se cumple (1 ≤ a ≤ b ≤ 10^18);2 ≤ p,q ≤ 10^9
Output
Imprima un número - cuantos números n entre a y b inclusive son p-dominante sobre q.
Sample test(s)
Input
1 20 3 2
Output
4