05/12/2025 15:50:20

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

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

03/11/2009	Тренировка (задачи Северного четвертьфинала 2009) (J)
17/07/2020	Летние сборы - 9 (командное) (J)