PRIMEPW - Lũy thừa số nguyên tố
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Với hai số nguyên a, x, trong đó x là số nguyên tố, ta định nghĩa hàm f(a, x) = k với a chia hết cho xk và k lớn nhất

Cho hai số nguyên a, b và hai số nguyên tố p, q. Hãy đếm xem có bao nhiêu số nguyên n nằm trong đoạn [a; b] mà f(n, p) > f(p, q)

Input

4 số nguyên a, b, p, q (1 <= a <= b <= 1018, 2 <= p, q <= 109, p khác q)

Output

Số số nguyên n nằm trong đoạn [a; b]f(n, p) > f(n, q)

Ví dụ

  • input
    1 20 2 3
    output
    8
Back to Top