Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1265. Jealous Numbers
Элементы теории чисел, диофантовы уравненияПеребор, метод уменьшения размера задачи
Олимпиадные задачи на английском языке
| 03/11/2009 | Тренировка (задачи Северного четвертьфинала 2009) (J) |
| 17/07/2020 | Летние сборы - 9 (командное) (J) |
Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
Source: ACM ICPC NEERC Northern Subregional 2009
