Задача E для тренировки в сентябре
Первоисточник: ACM ICPC 2009 -2010, NEERC, Northern Subregional Contest St Petersburg, October 17, 2009
Задачу добавил: elena
Успешно сдано решений: 2
Problem J. Jealous NumbersTime limit: 3 seconds
Memory limit: 256 megabytes
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 alpha(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 alpha(n, p) > alpha(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.
Example
input.txt
1 20 3 2
output.txt
4
In the given example 3, 9, 15 and 18 are 3-dominating over 2.