Задача №1700. Ревнивые числа
В Нумберляндии проблема: простое число \(p\) ревнует к другому простому числу \(q\). Оно думает, что в интервале от \(a\) до \(b\) включительно содержится больше чисел, которые делятся на большую степень \(q\) чем на степень \(p\). Помогите \(p\) справиться с сомнениями. Пусть \(a(n, x)\) – максимальное \(k\), такое, что \(n\) делится нацело на \(x^k\). Будем называть число \(n\) \(p\)-доминирующим над числом \(q\) если \(a(n, p) > a(n, q)\). Необходимо определить, сколько чисел из интервала от \(a\) до \(b\) включительно являются \(p\)-доминирующими над \(q\).
Первая строка содержит четыре целых числа \(a, b, p, q (1 ≤ a, b ≤ 10^{18}, 1 ≤ p, q ≤ 10^9)\). \(p ≠ q, p\) и \(q\) — простые.
Выведите одно число — сколько чисел из интервала от \(a\) до \(b\) включительно являются \(p\)-доминирующими над \(q\).
В примере числа 3, 9, 15 и 18 являются 3 доминирующими над 2.
1 20 3 2
4