eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ревнивые числа

Ревнивые числа

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

В стране чисел проблема: простое число p ревнует другое простое число q. Оно думает, что существует больше чисел от a до b включительно, которые делятся на наибольшую степень q, чем p. Помогите p избавиться от ее чувств.

Пусть α(n, x) - наибольшее k такое что n делится на x^k. Будем говорить, что число n является p-доминирующим над q, если α(n, p) > α(n, q). Выясните, сколько чисел от a до b включительно являются p-доминирующими над q.

Входные данные

В одной строке заданы числа a, b, p и q (1ab10^18; 2p, q10^9; pq; p и q простые).

Выходные данные

Вывести количество чисел n между a и b включительно, которые являются p-доминирующими над q.

Пример

Входные данные #1
1 20 3 2
Выходные данные #1
4