C - Anti-Division Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 A,B,C,D が与えられます。A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を求めてください。

制約

  • 1\leq A\leq B\leq 10^{18}
  • 1\leq C,D\leq 10^9
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

A B C D

出力

A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を出力せよ。

入力例 1

4 9 2 3

出力例 1

2

5,7 が条件を満たします。

入力例 2

10 40 6 8

出力例 2

23

入力例 3

314159265358979323 846264338327950288 419716939 937510582

出力例 3

532105071133627368

Score : 300 points

Problem Statement

You are given four integers A, B, C, and D. Find the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

Constraints

  • 1\leq A\leq B\leq 10^{18}
  • 1\leq C,D\leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368