printРабочее место участника

printЗадачи

1265. Jealous Numbers

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

There is a trouble in Numberland, prime number `p` is jealous of another prime number `q`. She thinks that there are more integer numbers between `a` and `b`, inclusively, that are divisible by greater power of `q` than that of `p`. Help `p` to get rid of her feelings.
Let `α(n,\ x)` be maximal `k` such that `n` is divisible by `x^k`. Let us say that a number `n` is `p`-dominating over `q` if `α(n,\ p)>α(n,\ q)`. Find out for how many numbers between `a` and `b`, inclusive, are `p`-dominating over `q`.
Input
The first line of the input file contains `a`, `b`, `p` and `q` (`1\ ≤\ a\ ≤\ b\ ≤\ 10^18`; `2\ ≤\ p,\ q\ ≤\ 10^9`; `p\ ≠\ q`; `p` and `q` are prime).
Output
Output one number – how many numbers `n` between `a` and `b`, inclusive, are `p`-dominating over `q`.

Sample Input

1 20 3 2

Sample Output

4
In the given example 3, 9, 15 and 18 are 3-dominating over 2.
Source: ACM ICPC NEERC Northern Subregional 2009
loading