Problem:


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



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

Solution code:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A,B,C,D = map(int,input().split())
lcm = lcm(C,D)
print((B - A + 1) - ((B // D - (A - 1) // D) + (B // C - (A - 1) // C) - (B // lcm - (A - 1) // lcm)))

Submission status: Accepted

Solution code:
import fractions
def kansu(x, c, d):
  c_baisu = x//c
  d_baisu = x//d
  l = (c * d) // fractions.gcd(c, d)
  juhuku = x//l
  return x - c_baisu - d_baisu + juhuku
  
a, b, c, d = (int(i) for i in input().split())
print(kansu(b,c,d)-kansu(a-1,c,d))

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = map(int, input().split())

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

lcm_cd = lcm(C, D)

mod_ac = A % C
mod_ad = A % D
mod_lcm = A % lcm_cd

c_num = 0
d_num = 0
cd_num = 0

if mod_ac == 0:
    c_num = B//C - A//C + 1
else:
    c_num = B//C - A//C

if mod_ad == 0:
    d_num = B//D - A//D + 1
else:
    d_num = B//D - A//D

if mod_lcm == 0:
    cd_num = B//lcm_cd - A//lcm_cd + 1
else:
    cd_num = B//lcm_cd - A//lcm_cd

ans = B - A + 1 - (c_num + d_num - cd_num)
print(ans)

Submission status: Accepted

Solution code:
import fractions

a = list(map(int,input().split()))
A = a[0]
B = a[1]
C = a[2]
D = a[3]
CD = C*D//fractions.gcd(C, D)

#Aまでの個数
AC = (A-1)//C
AD = (A-1)//D
ACD = (A-1)//CD

#Bまでの個数
BC = B//C
BD = B//D
BCD = B//CD

ans = (B-A+1) - ((BC-AC)+(BD-AD)-(BCD-ACD)) 

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(x,y):
    return (x*y) // gcd(x,y)

A,B,C,D = map(int,input().split())

def query(a,b,k):
    r = a % k
    res = (b-(a-r))//k + (-r//k) + 1
    return res

ans = B - A + 1 - (query(A,B,C) + query(A,B,D) - query(A,B,lcm(C,D)))
print(ans)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    return x
def lcm(x,y):
    return x*y//gcd(x,y)
ans_b=b-b//c-b//d+b//lcm(c,d)
z=a-1
ans_a=z-z//c-z//d+z//lcm(c,d)
print(ans_b-ans_a)

Submission status: Accepted

Solution code:
def GCD(s, t):
    if s < t:
        s, t = t, s
    if t == 0:
        return s
    else:
        return GCD(t,s%t)

A, B, C, D = map(int, input().split())
E = C*D // GCD(C,D)
x = B // C - (A-1) // C
y = B // D - (A-1) // D
z = B // E - (A-1) // E
print(B-A-x-y+z+1)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        temp = a
        a = b
        b = temp
    if b == 0:
        return a
    else:
        r = a % b
        if r == 0:
            return b
        else:
            return gcd(b, r)

def lcm(a, b):
    g = gcd(a, b)
    return (a*b) // g

def count_baisuu(A, B, x): #AからBまでにxで割り切れる個数はどれだけか
    start = A
    stop = B
    modx_a = A % x
    if modx_a == 0:
        start = 0
        stop = B-A
    else:
        start = A-modx_a+x
        stop = B-start
        start = 0
    if stop < 0:
        return 0
    else:
        return 1 + stop // x 

A, B, C, D = map(int,input().split())
afromb = B-A+1 #B-A+1個の整数がある
cd_lcm = lcm(C, D)
#cの倍数,dの倍数, lcm(c,d)の倍数は最低でもいくつあるか
divc = count_baisuu(A, B, C)
divd = count_baisuu(A, B, D)
divcd = count_baisuu(A, B, cd_lcm)
print(str((B-A+1)-(divc+divd-divcd)))

Submission status: Accepted

Solution code:
import math
def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

A,B,C,D = map(int,input().split())

count = 0
lcm = C*D // gcd(C,D)


print(B - B//C - B//D + B//lcm - (A - 1 - (A-1)//C - (A-1)//D + (A-1)//lcm))

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


def lcm(a, b):
	return a * b // gcd (a, b)

A,B,C,D = map(int,input().split())
if A%C !=0:
  C_left = (A//C) + 1
else:
  C_left = (A//C)
C_right = (B//C)

if A%D !=0:
  D_left = (A//D) + 1
else:
  D_left = (A//D)
D_right = (B//D)
CD = lcm(C,D)
if A%(CD) !=0:
  CD_left = (A//(CD)) + 1
else:
  CD_left = (A//(CD))
CD_right = (B//(CD))

C_=C_right - C_left +1
D_=D_right - D_left +1
CD_=CD_right - CD_left +1
print(B-A+1-C_-D_+CD_)

Submission status: Accepted

Solution code:
from fractions import gcd
def gcm(a,b):
    k = a * b / gcd(a,b)
    return int(k)

A,B,C,D = map(int,input().split())
bk = B - B//C - B//D + B//gcm(C,D)
ak = (A-1) - (A-1)//C - (A-1)//D + (A-1)//gcm(C,D)

print(bk-ak)

Submission status: Accepted

Solution code:
def s_y_n(x, y):
    if y == 0:
        return x
    else:
        return s_y_n(y, x % y)


def s_b_n(x, y):
    return x * y // s_y_n(x, y)


a, b, c, d = map(int, input().split())
bc = b // c
ac = (a-1) // c
bd = b // d
ad = (a-1) // d
bco = b // s_b_n(c, d)
aco = (a-1) // s_b_n(c, d)

print((b-a+1) - (bc-ac) - (bd-ad) + (bco-aco))

Submission status: Accepted

Solution code:
import math
import fractions

A, B, C, D = map(int, input().split())

def lcm(a, b):
  return (a * b) // fractions.gcd(a, b)

# Cで割り切れる数
divC = B // C - (A-1) // C

# Dで割り切れる数
divD = B // D - (A-1) // D

# CとDの最小公倍数で割り切れる数
lcmCD = lcm(C, D)
divCD = B // lcmCD - (A-1) // lcmCD

# CとDの少なくとも一方で割り切れる数
divCorD = divC + divD - divCD

# AからBまでの数
AB = B - A + 1

print(AB - divCorD)

Submission status: Accepted

Solution code:

import math
import fractions

A, B, C, D = map(int, input().split())

def lcm(a, b):
  return (a * b) // fractions.gcd(a, b)

# CとDの最小公倍数で割り切れる数
lcm = lcm(C, D)

ans = B-A+1 - (B//C-(A-1)//C) - (B//D-(A-1)//D) + (B//(lcm)-(A-1)//(lcm))

print(ans)

Submission status: Accepted

Solution code:
import fractions

def lcm(x, y):
    return x*y//fractions.gcd(x, y)

def func(n, p, q):
    return n - (n//p + n//q - n//lcm(p, q))

a, b, c, d = map(int,input().split())

print(func(b, c, d) - func(a-1, c, d))

Submission status: Accepted

Solution code:
import fractions

A,B,C,D = map(int, input().split())


c_and_d=C*D
#CとDの最小公倍数を求める
lcm = int(C*D//fractions.gcd(C,D))


count_C =0
count_D =0
count_C_and_D =0

count_C = int(B//C)-int((A-1)//C)
count_D = int(B//D)-int((A-1)//D)
count_C_and_D = int(B//lcm)-int((A-1)//lcm)

print(int((B-A+1) -(count_C + count_D - count_C_and_D)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
    
a, b, c, d = map(int,input().split())
def cal(i, j, k):
    return i // j + i // k - i // lcm(j, k)

if a % c == 0 or a % d == 0:
    print(b - a - (cal(b, c, d) - cal(a, c, d)))
else:
    print(b - a - (cal(b, c, d) - cal(a, c, d)) + 1)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())

def gcd(x,y): #最大公約数を求める
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

def fai(n,x,y): #n以下の整数のうち、xでもyでも割り切れる整数の個数
    g=gcd(x,y) #xとyの最大公約数
    l=x//g*y #xとyの最小公倍数。切り捨てでなくても大丈夫
    return n-(n//x)-(n//y)+(n//l)
    #全体-xの倍数の個数-yの倍数の個数+xとyの倍数の個数

print(fai(b,c,d)-fai(a-1,c,d))

Submission status: Accepted

Solution code:
import fractions

A,B,C,D = map(int, input().split())
lcm_number = C*D // fractions.gcd(C, D)
all_number = B -A + 1

answer_C = B // C - (A-1) // C
answer_D = B // D - (A-1) // D
answer_lcm = B // lcm_number - (A-1) // lcm_number

print(all_number - answer_C - answer_D + answer_lcm)

Submission status: Accepted

Solution code:
A, B, C, D = list(map(int,input().split()))
A = A - 1

def gcd(c, d):
    c, d= max(c, d), min(c, d)
    if c % d == 0:
        return d
    else :
        while c % d != 0:
            c, d = d, c % d
        return d

L = C * D // gcd(C, D)

ans = B - A - ( B // C - A // C + B // D - A // D - B // L + A // L)
print(ans)

Submission status: Accepted

Solution code:
import fractions

A,B,C,D=map(int,input().split())
lcm=C*D//fractions.gcd(C,D)

print((B-A+1)-((B//C+B//D-B//lcm) - (((A-1)//C+(A-1)//D-(A-1)//lcm))))

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = map(int, input().split())

divc = B//C - (A-1)//C
divd = B//D - (A-1)//D
lcm = C*D // fractions.gcd(C, D)
divgcd = B//lcm - (A-1)//lcm

print((B-A+1) - divc - divd + divgcd)

Submission status: Accepted

Solution code:
import math


def lem(A, B):
    AB = A * B
    while B != 0:
        A, B = B, A % B
    return AB // A


a, b, c, d = map(int, input().split())


bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = b - a+1 - bsep + asep
print(ans)

Submission status: Accepted

Solution code:
import math


def lem(A, B):
    AB = A * B
    while B != 0:
        A, B = B, A % B
    return AB // A


a, b, c, d = map(int, input().split())

"""
# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(int(not_d))
 """

total = b - a+1
bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = total - bsep + asep
print(ans)

Submission status: Accepted

Solution code:
""" import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(int(not_d))
 """

a, b, c, d = map(int, input().split())

total = b - a + 1


def lem(A, B):
	AB = A * B
	while B != 0:
		A, B = B, A % B
	return AB // A


bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = total - bsep + asep
print(ans)

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())

total = b - a + 1

def lem(A,B):
	AB = A * B
	while B != 0:
		A,B = B,A%B
	return AB // A

bsep = (b // c) + (b // d) - (b // lem(c,d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c,d)

ans = total - bsep + asep
print(ans)

Submission status: Accepted

Solution code:
def gcd(i,j):
  if i > j:
    tmp = i
    i = j
    j = tmp
  while i != 0:
    tmp = i
    i = j%i
    j = tmp
  return j
def lcm(i,j):
  return i*j//gcd(i,j)  
def main():
  a,b,c,d = map(int,input().split())
  ans = b-a+1
  ans -= (b//c - (a-1)//c) + (b//d - (a-1)//d) - (b//lcm(c,d) -(a-1)//lcm(c,d))
  print(ans)


main()

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

def lcm(x,y):
    return x*y//gcd(x,y)
p=lcm(c,d)
def f(n):
    return b//n-(a-1)//n
ans=b-a+1-f(c)-f(d)+f(p)
print(ans)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())

gcd = fractions.gcd(C, D)
lcm = C * D // gcd
a_c = (A-1) // C
a_d = (A-1) // D
b_c = B // C
b_d = B // D
a_lcm = (A-1) // lcm
b_lcm = B // lcm
count = (B - A + 1) - ((b_c - a_c) + (b_d - a_d) - (b_lcm - a_lcm))
print(int(count))

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    return gcd(b, a % b) if b > 0 else a


A, B, C, D = map(int, input().split())


def calc(n: int, div: int) -> int:
    assert div > 0
    return n // div


def calc2(l: int, r: int, div: int) -> int:
    assert r >= l
    assert div > 0
    return calc(r, div) - calc(l - 1, div)


lcm = (C * D) // gcd(C, D)

k = calc2(A, B, C) + calc2(A, B, D) - calc2(A, B, lcm)
print(B - A + 1 - k)

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x

A,B,C,D = map(int, input().split())
B_C = B // C
B_D = B // D
g = gcd(C,D)
l = C * D // g
duplicate_B = B // l
answer_B = B - B_C - B_D + duplicate_B

A_C = (A - 1) // C
A_D = (A - 1) // D
duplicate_A = (A - 1) // l
answer_A = (A - 1) - A_C - A_D + duplicate_A
print(int(answer_B - answer_A))

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
e = gcd(c,d)
f = c * d // e

b_c = b // c
s_c = (a-1) // c
C = b_c - s_c

b_d = b // d
s_d = (a-1) // d
D = b_d - s_d

b_cd = b // f
s_cd = (a-1) // f
CD = b_cd - s_cd

ans = b - a + 1 - (C + D - CD)
print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions
input = sys.stdin.readline
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)


A, B, C, D = map(int, input().split())
lcm=lcm(C,D)
ans = B-A+1 - (B//C-(A-1)//C) - (B//D-(A-1)//D) + (B//(lcm)-(A-1)//(lcm)) 


print(ans)

Submission status: Accepted

Solution code:
from fractions import Fraction
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def judge(a,c,d):
  x = a//c
  y = a//d
  z = a//lcm(d,c)
  return a-x-y+z

a,b,c,d = map(int,input().split())
#print(judge(a-1,c,d))
#print(judge(b,c,d))
ans = judge(b,c,d) - judge(a-1,c,d)
print(ans)

Submission status: Accepted

Solution code:
import fractions

a, b, c, d = map(int, input().split())
one_to_b = b // c + b // d
one_to_a = (a - 1) // c + (a - 1) // d
l = c * d // fractions.gcd(c, d)
dup = b // l - (a - 1) // l
dividable = one_to_b - one_to_a - dup
print(b - a + 1 - dividable)

Submission status: Accepted

Solution code:
import fractions

def lcm(a,b):
        return (a*b)//fractions.gcd(a,b)

a,b,c,d=map(int,input().split())
until_b = b-(b//c)-(b//d)+(b//lcm(c,d))
until_a = (a-1)-((a-1)//c)-((a-1)//d)+((a-1)//lcm(c,d))
print(until_b-until_a)

Submission status: Accepted

Solution code:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

a,b,c,d=map(int, input().split())
cd=lcm(c, d)

cc=b//c - (a-1)//c
dc=b//d - (a-1)//d
cdc=b//cd - (a-1)//cd

print(b-(a-1)-cc-dc+cdc)

Submission status: Accepted

Solution code:
import fractions

d = [int(x) for x in input().split()]
lcm = int(d[2] * d[3] // fractions.gcd(d[2], d[3]))
b = d[1] - int(d[1] // d[2]) - int(d[1] // d[3]) + int(d[1] // lcm)
a_1 = d[0] - 1
a = a_1 - int(a_1 // d[2]) - int(a_1 // d[3]) + int(a_1 // lcm)
print(b - a)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())

def eg(a, b):
    amari = max(a,b)%min(a,b)
    if amari == 0:
        return min(a,b)
    return eg(min(a,b), amari)

g = eg(C, D)
l = C*D // g

countB = B - (B // C + B // D) + B // l
countA = (A-1) - ((A-1) // C + (A-1) // D) + (A-1) // l

print(countB - countA)

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
 

lcm = C*D//fractions.gcd(C, D)

a_cnt = (A -1) - (((A - 1) // C) + ((A - 1) // D) - ((A - 1) // (lcm)))
b_cnt = B - ((B // C) + (B // D) - (B // (lcm)))

print(b_cnt - a_cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def euclid(a, b):
    if a > b:
        large = a
        small = b
    else:
        large = b
        small = a

    while small != 0:
        r = large % small
        large = small
        small = r

    return large


def solve(inputs):
    [A, B, C, D] = string_to_int(inputs[0])
    cd_gcd = euclid(C, D)
    cd_lcm = (C*D) // cd_gcd

    a_c = (A-1) // C
    a_d = (A-1) // D
    a_cd = (A-1) // cd_lcm

    b_c = B // C
    b_d = B // D
    b_cd = B // cd_lcm

    under_a = int((A-1) - a_c - a_d + a_cd)
    under_b = int(B - b_c - b_d + b_cd)

    return under_b - under_a


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)

Submission status: Accepted

Solution code:
import fractions

A,B,C,D = map(int,input().split())

gcd = fractions.gcd(C,D)
lcm = int(C*D/gcd)

ans_A = int((A-1) - (A-1)//C - (A-1)//D + (A-1)//lcm)
ans_B = int(B - B//C - B//D + B//lcm)
print(ans_B - ans_A)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import fractions

A, B, C, D = map(int,input().split())

lcm = C * D // fractions.gcd(C, D)

maxC = B // C
maxD = B // D
maxlcm = B // lcm

minC = (A-1) // C
minD = (A-1) // D
minlcm = (A-1) // lcm

lcmB = (maxC + maxD - maxlcm)
lcmA = (minC + minD - minlcm)

print((B-A+1)-(lcmB-lcmA))

Submission status: Accepted

Solution code:
def gcd(x,y):
    amari = max(x,y)%min(x,y)
    if amari == 0:
        return min(x,y)
    return gcd(min(x,y), amari)
def calc_scm(x,y,gcd):
    return x*y//gcd

A,B,C,D = list(map(int, input().split()))
scm = calc_scm(C,D,gcd(C,D))
low = (A-1)//C + (A-1)//D - (A-1)//scm
high = B//C + B//D - B//scm
print(B - A + 1 - (high - low))

Submission status: Accepted

Solution code:
A,B,C,D=map(int, input().split())
def gcd(a, b):
    remainder = max(a, b) % min(a, b)
    if remainder == 0:
        return min(a, b)
    return gcd(min(a, b), remainder)

def lcm(a, b):
    return a*b // gcd(a, b)

def f(X, a, b):
    return (X - X//a - X//b + X//lcm(a, b))

sum = f(B, C, D) - f(A-1, C, D)
print(sum)

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
a-=1
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b) # int

print(b-b//c-b//d+b//lcm(c,d)-(a-a//c-a//d+a//lcm(c,d)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def great_common_divisor(a, b):
    '''Calculate the great common divisor (GCD) of a and b
    Args:
        a (int) : value
        b (int) : value
    Returns:
        gcd (int) : the great common divisor of a and b
    Note:
        This function uses Euclidean Algorithm
    '''
    while b != 0:
        a, b = b, a % b
    return a

def least_common_multiple(a, b):
    '''Calculate the least common multiple (LCM) of a and b
    Args:
        a (int) : value
        b (int) : value
    Returns:
       lcm (int) : the least common multiple of a and b
    '''
    return (a * b) // great_common_divisor(a, b)



def solve(A: int, B: int, C: int, D: int):
    lcm = least_common_multiple(C, D)

    num_B = (B - B // C - B // D + B // lcm)

    # 「以上」「以下」の境界値に注意する。
    A = A - 1
    num_A = (A - A // C - A // D + A // lcm)

    print(num_B - num_A)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(p, q):
    if p % q == 0:
        return q
    else:
        return gcd(q, p % q)


def lcm(p, q):
    return p * q // gcd(p, q)


a, b, c, d = list(map(int, input().split()))
a_ = a - 1
bn = b - (b // c + b // d - b // lcm(c, d))
an = a_ - (a_ // c + a_ // d - a_ // lcm(c, d))
n = bn - an
print(n)

Submission status: Accepted

Solution code:
def calc_gcd(x,y):
    amari = max(x,y)%min(x,y)
    if amari == 0:
        return min(x,y)
    return calc_gcd(min(x,y), amari)
def calc_scm(x,y,gcd):
    return x*y//gcd

A,B,C,D = list(map(int, input().split()))
scm = calc_scm(C,D,calc_gcd(C,D))
low = (A-1)//C + (A-1)//D - (A-1)//scm
high = B//C + B//D - B//scm
print(B - A + 1 - (high - low))

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
l = c*d // gcd(c, d)
x = (a-1) - (a-1)//c - (a-1)//d + (a-1)//l
y = b - b//c - b//d + b//l
print(y-x)

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int, input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
	
e = round(c * d / gcd(c, d))

f=(a-1)//c
g=b//c
h=(a-1)//d 
k=b//d
l=(a-1)//e
m=b//e

x=(b-a+1)
y=g-f
z=k-h
w=m-l

print(x-y-z+w)

Submission status: Accepted

Solution code:
import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


if __name__ == '__main__':
    A, B, C, D = map(int, input().split())

    # A以上B以下の数
    between_A_B = B - A + 1

    # B以下でCで割り切れる数
    max_num_diveided_by_C = (B//C)

    # A未満でCで割り切れる数
    min_num_diveided_by_C = ((A-1)//C)

    # B以下でDで割り切れる数
    max_num_diveided_by_D = (B//D)

    # A未満でDで割り切れる数
    min_num_diveided_by_D = ((A-1)//D)

    # B以下でCでもDでも割り切れる数
    max_num_diveided_by_CD = (B//lcm(C, D))

    # A未満でCでもDでも割り切れる数
    min_num_diveided_by_CD = ((A-1)//lcm(C, D))

    answer = between_A_B - ((max_num_diveided_by_C - min_num_diveided_by_C) + (max_num_diveided_by_D - min_num_diveided_by_D) - (max_num_diveided_by_CD - min_num_diveided_by_CD))
    print(answer)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())


def gcd(a, b):
    if b > a:
        return gcd(b, a)
    
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b, r)


def count(n, c, d):
    n_c = n // c
    n_d = n // d
    g = gcd(c, d)
    n_cd = n // (c * d // g)
    return n - n_c - n_d + n_cd


print(count(B, C, D) - count(A - 1, C, D))

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
c_=0
d_=0
n=0
if a%c!=0 and b>c:
    c_= a+c-a%c #12
    n+=1
elif b<c:
    c_= b
else:
    c_ = a
    n+=1
if a%d!=0 and b>d:
    d_= a+d-a%d #16
    n+=1
elif b<d:
    d_= b
else:
    d_ = a
    n+=1
r = max(c,d)%min(c,d)
b_=min(c,d)
while r!=0:
    a_= b_
    b_=r
    r=a_%b_
e = int(c*d/b_)
if a%e!=0 and b>e:
    e_= a+e-a%e #48
    n-=1
elif b<e:
    e_= b
else:
    e_ = a
    n-=1
n += (b-c_)//c+(b-d_)//d-(b-e_)//e
print(1+b-a-n)

Submission status: Accepted

Solution code:
import fractions

abcd = list(map(int, input().split()))
a = abcd[0]
b = abcd[1]
c = abcd[2]
d = abcd[3]

aa = a - 1
lcm = (c * d) // fractions.gcd(c, d)

a_count = aa - (aa // c) - (aa // d) + (aa // lcm)
b_count = b - (b // c) - (b // d) + (b // lcm)

print(b_count - a_count)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(x,y):
    if x==0:
        return y
    else:
        return gcd(y%x,x)
def lcm(x,y):
    return x*y//gcd(x,y)
 
e=lcm(c,d)
ans=0
ans=b//c-(a-1)//c+b//d-(a-1)//d
ans-=b//e-(a-1)//e
print(b-a+1-ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a*b // gcd(a, b)

A, B, C, D = map(int, input().split())
CD = lcm(C, D)

divC = B//C - (A-1)//C
divD = B//D - (A-1)//D
divCD = B//CD - (A-1)//CD

cnt = B-A+1 - divC - divD + divCD
print(cnt)

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int, input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
	
e = (c * d // gcd(c, d))
 
 
f=(a+c-1)//c
g=b//c
h=(a+d-1)//d
k=b//d
l=(a+e-1)//e
m=b//e
x=b-a+1
y=g-f+1
z=k-h+1
w=m-l+1
print(x-y-z+w)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return(y)

a,b,c,d = map(int,input().split())
cd = gcd(c,d)
cd = c*d//cd

c_num  = (b//c)-(a//c)
d_num  = (b//d)-(a//d)
cd_num = (b//(cd))-(a//(cd))

if a%c == 0:
    c_num = c_num+1

if a%d == 0:
    d_num = d_num+1

if a%(cd) == 0:
    cd_num = cd_num+1

if c%d == 0:
    print(b-a+1-d_num)
elif d%c ==0:
    print(b-a+1-c_num)
else:
    print(b-a+1-c_num-d_num+cd_num)

Submission status: Accepted

Solution code:
import fractions
x = input().split()
a,b,c,d = int(x[0]),int(x[1]),int(x[2]),int(x[3])

cd = int(c*d/fractions.gcd(c,d))

cn = b // c - (a-1) // c
dn = b // d - (a-1) // d
cdn = b // cd - (a-1) // cd

print((b-a+1)-(cn+dn-cdn))

Submission status: Accepted

Solution code:
def gcd(a,b):
  if a<b:
    a,b = b,a
  while b!=0:
    a,b=b,a%b
  return a
   
def lcm(a,b):
  return a*b//gcd(a,b)

A,B,C,D = list(map(int, input().split()))

cnum = B // C - (A-1) // C
dnum = B // D - (A-1) // D
xnum = B // lcm(C,D) - (A-1) // lcm(C,D)

#print(cnum, dnum, xnum)
print(B - A + 1 - (cnum + dnum - xnum))

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))

Submission status: Accepted

Solution code:
import fractions

a,b,c,d=map(int,input().split())
e=b-a+1
f=b//c
g=b//d
h=(a-1)//c
i=(a-1)//d
j=c*d//fractions.gcd(c,d)
k=b//j
l=(a-1)//j
m=e-(f-h)-(g-i)+(k-l)
print(m)

Submission status: Accepted

Solution code:
from fractions import gcd
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
 
a, b, c, d = map(int, input().split())
 
yaku_b = b - (b // c + b // d - b // lcm(c,d))
yaku_a = a-1 - ((a-1) // c + (a-1) // d - (a-1) // lcm(c,d))
print(yaku_b - yaku_a)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
if C > D:
  C, D = D, C
c, d = C, D
while True:
  c, d = d%c, c
  if c == 0:
    break
E = C*D//d
#print(d, E)
r = (B-A+1)-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//E-(A-1)//E)
print(r)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a*b//(gcd(a, b))

def num(n, c, d):
    dc = n//c
    dd = n//d
    dcd = n//(lcm(c, d))
    return n-dc-dd+dcd

a, b, c, d = map(int, input().split())
print(num(b, c, d) - num(a-1, c, d))

Submission status: Accepted

Solution code:
def gcd(a, b):
	while (b != 0):
		temp = a % b
		a = b
		b = temp
	return abs(a)

a, b, c, d = map(int, input().split())
x = c*d//gcd(c, d)
print((b-a+1)-(b//c-(a-1)//c+b//d-(a-1)//d-b//x+(a-1)//x))

Submission status: Accepted

Solution code:
A,B,C,D=list(map(int, input().split()))

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def lcm(a,b):
  return a*b//gcd(a,b)

E=lcm(C,D)

A-=1

Cmin=A-A%C
Cmax=B-B%C
Dmin=A-A%D
Dmax=B-B%D
Emin=A-A%E
Emax=B-B%E

num = ((Cmax-Cmin)//C)+((Dmax-Dmin)//D)-((Emax-Emin)//E)



print(int(B-A-num))

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

def lcm(C, D):
    g = gcd(C, D)
    G = D * C // g
    return G

def num(A, C, D):
    G = lcm(C, D)
    return A - A // C - A // D + A // G

print("{}".format(num(B, C, D) - num(A-1, C, D)))

Submission status: Accepted

Solution code:
def euclideanAlgo(a,b):
    cond = True
    while cond:
        mod = a%b
        if mod == 0:
            cond = False
            return(b)
        a = b
        b = mod

a,b,c,d = map(int, input().split())
e = (c*d)//euclideanAlgo(c,d)
ALL = b-a+1
c_kosuu = b//c-(a-1)//c
d_kosuu = b//d-(a-1)//d
e_kosuu = b//e-(a-1)//e
print(ALL -c_kosuu - d_kosuu +e_kosuu)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int, input().split())
if a % c == 0:
    div_c = b//c - a//c +1
else:
    div_c = b//c - a//c 
if a % d == 0:
    div_d = b//d - a//d + 1
else:
    div_d = b//d - a//d
x = c*d // gcd(c,d)
if a % x == 0:
    div_cd = b//x - a//x + 1
else:
    div_cd = b//x - a//x
print(b-a+1 - div_c -div_d + div_cd)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())

def gcd(a,b):
    if a<b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b,a%b)
    
lcm = C*D//gcd(C,D)

bDivC = B // C
bDivD = B // D
bDivCD = B // lcm
numBDividable = bDivC + bDivD - bDivCD
numB = B - numBDividable

aDivC = (A-1) // C
aDivD = (A-1) // D
aDivCD = (A-1) // lcm
numADividable = aDivC + aDivD - aDivCD
numA = A-1 - numADividable

answer = numB - numA
print(answer)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split(' '))

def gcd(a, b):
  if(a==0):
    return b  
  c = b%a  
  return gcd(c,a)

def lsm(a, b):
  return a * b // gcd(a, b)

result= B//C+B//D-B//lsm(C,D) -((A-1)//C+(A-1)//D-(A-1)//lsm(C,D))
print(B-A+1-result)

Submission status: Accepted

Solution code:

a, b, c, d = map(int, input().split())

def gcd (a, b):
    while b != 0:
        a, b = b, a % b
    return a
gcd = gcd(c, d)

large_c = b // c
large_d = b // d
large_cd = b // ((c * d) // gcd)
large = large_c + large_d - large_cd

small_c = (a - 1) // c
small_d = (a - 1) // d
small_cd = (a - 1) // ((c * d) // gcd)
small = small_c + small_d - small_cd

print(int((b - (a - 1)) - (large - small)))

Submission status: Accepted

Solution code:
import fractions

A,B,C,D = map(int,input().split())

f = fractions.gcd(C,D)
f_1 = C*D//f

ans_1 = B-(B//C + B//D - B//f_1)
ans_2 = (A-1)-((A-1)//C + (A-1)//D - (A-1)//f_1)
print(ans_1-ans_2)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(a,b):
    return a * b // gcd(a,b)
    
a, b, c, d = map(int, (input().split()))

ans = b - a + 1
ans += (b // lcm(c, d) - (a-1) // lcm(c, d))
ans -= (b // c - (a-1) // c) + (b // d - (a-1) // d)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
a,b,c,d = map(int,input().split())
a-=1
print((b-a)-(b//c+b//d-a//c-a//d-(b//lcm(c,d))+(a//lcm(c,d))))

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = (int(i) for i in input().split())


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


one_to_b = B - ((B // C) + (B // D) - (B // lcm(C, D)))
one_to_a = A - 1 - ((((A - 1) // C) +
                     ((A - 1) // D) -
                     (A - 1) // lcm(C, D)))

print(one_to_b - one_to_a)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())

def gcd(a, b):
  if a == 0:
    return b
  return gcd(b%a, a)

g = gcd(C, D) if C < D else gcd(D, C)
ansB = B-B//C-B//D+B//(C*D//g)
ansA = A - 1 - (A-1)//C - (A-1)//D + (A-1)//(C*D//g)
print(ansB-ansA)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())
n = B-A+1
c1 = n//C
d1 = n//D
cd = C*D//fractions.gcd(C, D)
cd1 = n//(cd)
if ((A+c1*C-1)%C + (B-(A+c1*C-1))) // C == 1:
    c1 += 1
if ((A+d1*D-1)%D + (B-(A+d1*D-1))) // D == 1:
    d1 += 1
if ((A+cd1*cd-1)%(cd) + (B-(A+cd1*cd-1))) // cd == 1:
    cd1 += 1
print(n-(c1+d1-cd1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def gcd(a, b):
    if b != 0:
        return gcd(b, a%b)
    else:
        return a

a, b, c, d = map(int, input().split())
lcd = c*d//gcd(c, d)
a -= 1
ans = (b - b//c - b//d + b//lcd) - (a - a//c - a//d + a//lcd)
print(ans)