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

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


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


a = (A-1) // C
b = B // C
c = (A-1) // D
d = B // D
x = lcm(C, D)
e = (A-1) // x
f = B // x

print(B - A + 1 - ((b - a) + (d - c) - (f - e)))

Solution (Python):
def lcm(a, b):
    from fractions import gcd
    return (a * b) // gcd(a, b)


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

all_warikire = B - (B // C) - (B // D) + B // LCM
sub_warikire = A - (A // C) - (A // D) + A // LCM

print(all_warikire - sub_warikire)

Solution (Python):
import math
A,B,C,D = (int(x) for x in 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)
lcm = lcm(C,D)

if A-1 < C:
  fst = B//C
else:
  fst = B//C - (A-1)//C

if A-1 < D:
  snd = B//D
else:
  snd = B//D - (A-1)//D

if A-1 < lcm:
  dlt = B//lcm
else:
  dlt = B//lcm - (A-1)//lcm

print(B-A+1 - (fst+snd-dlt))

Solution (Python):
A, B, C, D = 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)

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

Solution (Python):
import fractions

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

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

Sum_A = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//(Min))
Sum_B = B - (B//C + B//D - B//(Min))
Sum = Sum_B - Sum_A

print(Sum)

Solution (Python):
import fractions
def LCM(a,b):
    return int(a*b/fractions.gcd(a,b))
A,B,C,D = map(int,input().split())
L = LCM(C,D)
Cbaisu = (B//C) - ((A-1)//C)
Dbaisu = (B//D) - ((A-1)//D)
Lbaisu = (B//L) - ((A-1)//L)
print(B-A+1 - Cbaisu - Dbaisu + Lbaisu)

Solution (Python):



def gcd(m, n):
    if m < n:
        return gcd(n, m)
    if m % n == 0:
        return n
    return gcd(n, m % n)


def lcm(m, n):
    return n // gcd(m, n) * m


def solv(a, b, c, d):
    if b <= a:
        return 0

    lcm_cd = lcm(c, d)
    if a == 0:
        c0 = 0
    else:
        a = a - 1
        c0 = a - (a // c) - (a // d) + (a // lcm_cd)
    c1 = b - (b // c) - (b // d) + (b // lcm_cd)
    return c1 - c0


if __name__ == '__main__':

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

    
    

    ans = solv(a, b, c, d)

    print(ans)

Solution (Python):
a, b, c, d = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def divided_num(a,b,c):
    return b//c - a//c +1 if a%c==0 else b//c - a//c

print((b - a + 1) - divided_num(a,b,c) - divided_num(a,b,d) + divided_num(a,b,lcm(c, d)))

Solution (Python):
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

bc = B // C
bd = B // D
be = B // int((C*D/gcd(C, D)))
BB = B - bc - bd + be

ac = (A-1) // C
ad = (A-1) // D
ae = (A-1) // int(C*D/gcd(C, D))
AA = (A-1) - ac - ad + ae

print(BB-AA)

Solution (Python):
import math

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

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

a, b, c, d = map(int, input().split())
ran = b - a + 1

def count(x):
    r = ran if a % x == 0 else ran - (x - a % x)
    return r // x if r % x == 0 else r // x + 1

count1 = count(c)
count2 = count(d)
e = lcm(c, d)
count3 = count(e)
print(ran - (count1 + count2 - count3))

Solution (Python):
import fractions
a,b,c,d = map(int,input().split())
a = a-1
cd = fractions.gcd(c,d)
cm = c*d//cd
blk = cm - cm//c - cm//d + 1
M = (b//cm)*blk + b%cm - (b%cm)//c - (b%cm)//d
m = (a//cm)*blk + a%cm - (a%cm)//c - (a%cm)//d
print(int(M-m))

Solution (Python):


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

num = 0

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

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





print(str(num))

Solution (Python):
import sys,fractions
input = sys.stdin.readline

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


lcm =  (C*D)//fractions.gcd(C,D)
c=0
End = (B//C)+(B//D)-(B//(lcm))

Start = ((A-1)//C)+((A-1)//D)-((A-1)//(lcm))

print(int((B-A+1)-(End-Start)))

Solution (Python):


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

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


v = c*d//gcd(c,d)

s = b//c - (a-1)//c
t = b//d - (a-1)//d
u = b//v - (a-1)//v

print((b-a+1) - (s+t-u))

Solution (Python):
A, B, C, D = map(int, input().split())
max_cnt = B - A + 1
import fractions
lcm = int(C * D / fractions.gcd(C, D))
cnt_2 = B//C - (A-1)//C
cnt_3 = B//D - (A-1)//D
cnt_4 = B//lcm - (A-1)//lcm
print(max_cnt - cnt_2 - cnt_3 + cnt_4)

Solution (Python):

a=[]
a=input().split(" ")
A=int(a[0])
B=int(a[1])
C=int(a[2])
D=int(a[3])

def gcd(m,n):
    x=max(m,n)
    y=min(m,n)
    if x % y ==0:
        return y
    else:
        while x % y != 0:
            z=x%y
            x=y
            y=z
        else:
            return z

def lcm(m,n):
    return int(m*n/gcd(m,n))

X=lcm(C,D)
Y=B-A+1-(B//D-(A-1)//D)-(B//C-(A-1)//C)+(B//X-(A-1)//X)
print(Y)

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


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

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

cd = lcm(c,d)

mul_count = b//c + b//d - b//cd
a -= 1
mul_count -= (a//c + a//d -a//cd)
print(b - a - mul_count)

Solution (Python):
import fractions

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

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

tmp   = b-a+1
tmp_c = (b//c-(a-1)//c)
tmp_d = (b//d-(a-1)//d)
tmp_e = (b//lcm(c,d)-(a-1)//lcm(c,d))

print(tmp - tmp_c - tmp_d + tmp_e)

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

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

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

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

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

sa = B - A + 1

C2 = (B // C) - ((A - 1) // C)
D2 = (B // D) - ((A - 1) // D)

CD = lcm(C, D)

CD2 = (B // CD) - ((A - 1) // CD)

print(sa - (C2 + D2 - CD2))

Solution (Python):
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
a,b,c,d = map(int,input().split())
ans = b-a+1
dim = 0
ca = a % c
if not ca:
    dim +=1
da = a % d
if not da:
    dim +=1
cd = lcm(c,d)
cda = a%cd
if not cda:
    ans+=1
dim+= (b-a+ca)//c
dim+= (b-a+da)//d
ans += (b-a+cda)//cd
print(ans-dim)

Solution (Python):
import fractions
A, B, C, D = map(int, input().split())
divC=B//C-(A-1)//C
divD=B//D-(A-1)//D
CD=int(C*D/fractions.gcd(C, D))
divCD=B//(CD)-(A-1)//(CD)
print(B-A+1-(divC+divD-divCD))

Solution (Python):
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())
divC = B//C - (A-1)//C
divD = B//D - (A-1)//D
CD = lcm(C,D)
divCD = B//CD - (A-1)//CD
divsum=divC+divD-divCD
answer=B-A+1-divsum

print(answer)

Solution (Python):
import sys

readline = sys.stdin.readline

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

def get_gcd(x, y):
    while True:
        if x > y:
            t = x % y
            a = y
            x = t
        else:
            t = y % x
            a = x
            y = t
        if t == 0:
            return a

c = B // C - (A - 1) // C
d = B // D - (A - 1) // D
lcm = C * D // get_gcd(C, D)
cd = B // lcm - (A - 1) // lcm


ans = B - (A - 1) - (c + d - cd)

print(ans)

Solution (Python):
from fractions import gcd


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

cd = c * d // gcd(c, d)

div_by_c = b // c - (a-1) // c
div_by_d = b // d - (a-1) // d
div_both = b // cd - (a-1) // cd

dividable = div_by_c + div_by_d - div_both
non_dividable = (b - a + 1) - dividable

print(non_dividable)

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

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

n_c = B//C - (A-1)//C
n_d = B//D - (A-1)//D
lcm_cd = C*D // gcd(C,D)
n_cd = B//lcm_cd - (A-1)//lcm_cd

print(B-A+1 - (n_c+n_d-n_cd))

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

C_s = (A-A%C)//C
C_e = (B-B%C)//C

D_s = (A-A%D)//D
D_e = (B-B%D)//D

C_cnt = C_e - C_s
if A%C==0:
    C_cnt += 1
D_cnt = D_e - D_s
if A%D==0:
    D_cnt += 1

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

lcm_s = (A-A%lcm)//lcm
lcm_e = (B-B%lcm)//lcm

lcm_cnt = lcm_e - lcm_s
if A%lcm==0:
    lcm_cnt += 1

cnt = C_cnt + D_cnt - lcm_cnt
ans = B - A + 1 - cnt
print(ans)

Solution (Python):
import fractions
a,b,c,d = map(int,input().split())
a=a-1
x=(c*d)//fractions.gcd(c,d)
n=b//c-a//c
m=b//d-a//d
o=b//x-a//x
ans=b-a-n-m+o
print(ans)

Solution (Python):
a, b, c, d = 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)

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

print(x-y)

Solution (Python):

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())
l = []
cnt_c = 0
cnt_d = 0
n = b+1-a








lcm = lcm(c, d)

x = b//c - (a-1)//c
y = b//d - (a-1)//d
z = b//lcm - (a-1)//lcm


print(n-x-y+z)

Solution (Python):
import fractions
A,B,C,D = list(map(int,input().split()))
dis = B - A + 1

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

perCfromA = (A-1)//C
perDfromA = (A-1)//D
perCDfromA = (A-1)//(CD)


perCfromB = B//C
perDfromB = B//D
perCDfromB = B//(CD)


warikire = (perCfromB + perDfromB -perCDfromB) - (perCfromA + perDfromA -perCDfromA)
warikirenai = dis -warikire
print(warikirenai)

Solution (Python):
import fractions
a,b,c,d = map(int,input().split())
diff_c = b//c - (a-1)//c
diff_d = b//d - (a-1)//d
lcm_cd = int(c*d/fractions.gcd(c,d))
diff_cd = b//(lcm_cd) - (a-1)//(lcm_cd)
print((b-a+1)-(diff_c+diff_d-diff_cd))

Solution (Python):
import fractions


def main():
    def lcm(x, y):
        return (x * y) // fractions.gcd(x, y)
    A, B, C, D = map(int, input().split())
    l = lcm(C, D)
    print((B - (B//C + B//D - B//l)) -
          (A-1 - ((A-1)//C + (A-1)//D - (A-1)//l)))


if __name__ == "__main__":
    main()

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def unchi(x,m,n):
  r=x//m+x//n-x//(m*n//(gcd(m,n)))
  return r
a,b,c,d=(int(i) for i in input().split())
print(b-a+1-(unchi(b,c,d)-unchi(a-1,c,d)))

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

def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b

if a % c == 0:
    l = a
    if b % c == 0:
        r = b
    else:
        r = b - (b%c)
    if l > r:
        x = 0
    else:
        x = (r-l) // c + 1
else:
    l = a+(c-(a%c))
    if b % c == 0:
        r = b
    else:
        r = b - (b%c)
    if l > r:
        x = 0
    else:
        x = (r-l) // c + 1
if a % d == 0:
    l = a
    if b % d == 0:
        r = b
    else:
        r = b - (b%d)
    if l > r:
        y = 0
    else:
        y = (r-l) // d + 1
else:
    l = a+(d-(a%d))
    if b % d == 0:
        r = b
    else:
        r = b - (b%d)
    if l > r:
        y = 0
    else:
        y = (r-l) // d + 1
g = c*d//gcd(c,d)
if a % g == 0:
    l = a
    if b % g == 0:
        r = b
    else:
        r = b - (b%g)
    if l > r:
        z = 0
    else:
        z = (r-l) // g + 1
else:
    l = a+(g-(a%g))
    if b % g == 0:
        r = b
    else:
        r = b - (b%g)
    if l > r:
        z = 0
    else:
        z = (r-l) // g + 1
ans = b-a+1-x-y+z
print(ans)

Solution (Python):
def gcd(a, b):
    return gcd(b%a, a) if a else b
def lcm(a, b):
    return a * b // gcd(a, b)

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

total = B - A + 1

group_CD = lcm(C, D)

if A % C == 0:
    lower_C = A // C
else:
    lower_C = A // C + 1
upper_C = B // C + 1
num_C = upper_C - lower_C

if A % D == 0:
    lower_D = A // D
else:
    lower_D = A // D + 1
upper_D = B // D + 1
num_D = upper_D - lower_D

if A % group_CD == 0:
    lower_CD = A // group_CD
else:
    lower_CD = A // group_CD + 1
upper_CD = B // group_CD + 1
num_CD = upper_CD - lower_CD

print(total - num_C - num_D + num_CD)

Solution (Python):
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 = [int(s) for s in input().split()]
E = B-B//C-B//D+B//lcm(C,D)
Ap = A-1
F = Ap-Ap//C-Ap//D+Ap//lcm(C,D)
print(E-F)

Solution (Python):

def calGCD(x,y):
    while(y > 0):
        x, y = y, x % y
    return x

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

CD = C * D // calGCD(C,D)

cntC = (B // C) - (A // C)
cntD = (B // D) - (A // D)
cntCD = (B // CD) - (A // CD)

if A % C == 0:
    cntC += 1
if A % D == 0:
    cntD += 1
if A % CD == 0:
    cntCD += 1

ans = B - A + 1 - (cntC + cntD - cntCD)
print(ans)

Solution (Python):
def gcd(a, b):
    while b != 0:
        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())

first_c = c * (a // c + 1)
if a % c == 0:
    first_c -= c
last_c = c * (b // c)

first_d = d * (a // d + 1)
if a % d == 0:
    first_d -= d
last_d = d * (b // d)

cd = lcm(c, d)
first_cd = cd * (a // cd + 1)
if a % cd == 0:
    first_cd -= cd
last_cd = cd * (b // cd)

cnum = 0
dnum = 0
cdnum = 0

if first_c <= b:
    cnum = (last_c - first_c) // c + 1

if first_d <= b:
    dnum = (last_d - first_d) // d + 1

if first_cd <= b:
    cdnum = (last_cd - first_cd) // cd + 1

total = cnum + dnum - cdnum
print(b - a + 1 - total)

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

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

c1=B//C
c2=(A-1)//C

cd1=B//((C*D)//gcd(C,D))
cd2=(A-1)//((C*D)//gcd(C,D))

d1=B//D
d2=(A-1)//D


print(str(int(B-A+1-(c1-c2)-(d1-d2)+(cd1-cd2))))

Solution (Python):
import fractions

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

    def num_of_multiples(st, ed, m):
        a = st % m
        a0 = st + (m - a)
        if a == 0:
            a0 = st
        if a0 > ed:
            return 0
        b = ed % m
        b0 = ed - b
        num = (b0 - a0)
        if num % m != 0:
            raise Exception()
        return (b0 - a0) // m + 1
    
    nc = num_of_multiples(A, B, C)
    nd = num_of_multiples(A, B, D)
    ncd = num_of_multiples(A, B, C * D // fractions.gcd(C, D))
    print(B - A + 1 - (nc + nd - ncd))


main()

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

from fractions import gcd

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

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

print(b-a+1-hoge)

Solution (Python):
import fractions
a,b,c,d = map(int, input().split())

cd_gcd = fractions.gcd(c, d)
cd_lcm = (c*d)//cd_gcd

div_c_min = (a-1) // c
div_c_max = b // c
div_d_min = (a-1) // d
div_d_max = b // d
div_cd_min = (a-1) // (cd_lcm)
div_cd_max = b // (cd_lcm)

total =  b - a +1

diff = (div_c_max-div_c_min) + (div_d_max-div_d_min) - (div_cd_max - div_cd_min)
diff_total = total -diff

print(diff_total)

Solution (Python):
import sys

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


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


def main():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    E = lcm(C, D)

    total = B - A + 1
    multi_c = max(0, B // C) - max(0, A // C)
    if A % C == 0:
        multi_c += 1
    multi_d = max(0, B // D) - max(0, A // D)
    if A % D == 0:
        multi_d += 1
    multi_e = max(0, B // E) - max(0, A // E)
    if A % E == 0:
        multi_e += 1
    return total - (multi_c + multi_d - multi_e)


if __name__ == '__main__':
    print(main())

Solution (Python):

import sys





"""Template"""


class IP:
    """
    入力を取得するクラス
    """
    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        
        
        
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x//y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

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


"""ここからメインコード"""


def main():
    
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    a, b, c, d = ip.IL()
    memo = b - a + 1
    memo2 = id.lcm(c, d)
    a_c = (a-1) // c
    a_d = (a-1) // d
    b_c = b // c
    b_d = b // d
    b_cd = b // memo2
    a_cd = a // memo2
    if a % memo2 == 0:
        aaa = 1
    else:
        aaa = 0

    acd = a_c + a_d
    bcd = b_c + b_d
    kaburi = b_cd - a_cd
    
    
    
    ans = bcd - acd - kaburi - aaa
    print(memo - ans)


main()

Solution (Python):



import fractions

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def calc(n, x):
    return n // x

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

def main():
    a, b, c, d = rli()
    lcm_cd = lcm(c, d)
    n_a = a-1 - calc(a-1, c) - calc(a-1, d) + calc(a-1, lcm_cd)
    n_b = b - calc(b, c) - calc(b, d) + calc(b, lcm_cd)
    print(n_b-n_a)


if __name__ == '__main__':
    main()

Solution (Python):
a, b, c, d = map(int, input().split())
cc = c
dd = d
if cc < dd:
    cc, dd = dd, cc
while cc % dd != 0:
    cc, dd = dd, cc % dd
gcd = dd

sum = 0
mi = (a-1)//c
ma = b//c
sum += ma - mi

mi = (a-1)//d
ma = b//d
sum += ma - mi

cd = c * d // gcd
mi = (a-1)//cd
ma = b//cd
sum -= ma - mi
print(b-a-sum+1)

Solution (Python):
import fractions
A, B, C, D = map(int, input().split())
waric = 1 if A%C == 0 else 0
warid = 1 if A%D == 0 else 0
l = (C*D)//(fractions.gcd(C,D))
waricd = 1 if A%l == 0 else 0
cnd = B - A + 1 - (B//C - A//C + waric)
dnd = B - A + 1 - (B//D - A//D + warid) 
cdnd = B - A + 1 - (B//l - A//l + waricd)
print(cnd + dnd - cdnd)

Solution (Python):




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


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


def func(x):
    return x - x // c - x // d + x // l


def main():
    print(func(b)-func(a-1))


if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd

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

cnt = int(0)

for i in [c, d]:
    t4 = a // i
    if a % i == 0:
        t1 = t4
    else:
        t1 = t4+1
    t2 = b // i

    cnt += int(t2 - t1 + 1)

lcm = c * d // int(gcd(c, d))

i = lcm
t4 = a // i
if a % i == 0:
    t1 = t4
else:
    t1 = t4 + 1
t2 = b // i

cnt -= int(t2 - t1 + 1)

print(b - a + 1 - cnt)

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a

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

lcm = c * d // gcd(c, d)

count = b // c - a // c
if a % c == 0:
    count += 1

count += b // d - a // d
if a % d == 0:
    count += 1

count -= (b // lcm - a // lcm)
if a % lcm == 0:
    count -= 1

print((b - a) + 1 - count)

Solution (Python):
from math import ceil,floor
A,B,C,D = map(int,input().split())

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

def keisan(s,e,d):
    if s%d == 0:
        return e//d - s//d + 1
    else:
        return e//d - s//d

if B == A:
    if A%C == 0 or A%D == 0:
        print(0)
    else:
        print(1)
else:
    print(B-A+1-(keisan(A,B,C)+keisan(A,B,D)-keisan(A,B,lcm(C,D))))

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

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

def main():
    A, B, C, D = map(int, input().split())
    B_C = B // C
    B_D = B // D
    A_C = (A-1) // C
    A_D = (A-1) // D
    min_lcm = lcm(C, D)
    B_min_lcm = B // min_lcm
    A_min_lcm = (A-1) // min_lcm
    x = (B - A + 1) - ((B_C - A_C) + (B_D - A_D) - (B_min_lcm - A_min_lcm))
    print(x)

if __name__ == "__main__":
    main()

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

def ans(v1,v2,v3):
    return v1-v1//v2-v1//v3+v1//(v2*v3//fractions.gcd(v2,v3))
print(int(ans(B,C,D)-ans(A-1,C,D)))

Solution (Python):
from sys import stdin
input = stdin.readline().split()
A, B, C, D = int(input[0]), int(input[1]), int(input[2]), int(input[3])
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x % y
            x = y
            y = z
        else:
            return z
def lcm(m, n):
    return int(m * n / gcd(m, n))

val_lcm = lcm(C, D)

b_c = B // C
b_d = B // D
a_c = (A - 1) // C
a_d = (A - 1) // D
b_lcm = B // val_lcm
a_lcm = (A - 1) // val_lcm
dif_c = b_c - a_c
dif_d = b_d - a_d
dif_lcm = b_lcm - a_lcm

print(B - A + 1 - (dif_c + dif_d) + dif_lcm)

Solution (Python):
import fractions
a, b, c, d = (int(i) for i in input().split())

ABc = b // c - (a - 1) // c
ABd = b // d - (a - 1) // d
cd = c * d // fractions.gcd(c, d)
ABcd = b // cd - (a - 1) // cd

print(b - a + 1 - (ABc + ABd - ABcd))

Solution (Python):
from sys import stdin

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
A,B,C,D = map(int,stdin.readline().rstrip().split())
lcm=(C * D) // gcd(C, D)

AdivLcm=A//lcm
BdivLcm=B//lcm
ABdivLcmNum=BdivLcm-AdivLcm
if A%lcm==0:
  ABdivLcmNum+=1

AdivC = A//C
BdivC = B//C
ABdivCNum = BdivC-AdivC
if A%C==0:
  ABdivCNum+=1

AdivD = A//D
BdivD = B//D
ABdivDNum = BdivD-AdivD
if A%D==0:
  ABdivDNum+=1

candiv=ABdivCNum+ABdivDNum-ABdivLcmNum
print(B-A+1-candiv)

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


def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        else:
            return z

def lcm (m,n):
    return int(m * n / gcd(m,n))

div_C = (B//C) - ((A // C - 1) if A % C == 0 else (A // C))
div_D = (B//D) - ((A // D - 1) if A % D == 0 else (A // D))
mul = lcm(C,D)
div_mul = (B//mul) - ((A // mul - 1) if A % mul == 0 else (A // mul))
ans = (B - A + 1) - (div_C + div_D - div_mul)
print(ans)

Solution (Python):
def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)
  
a = [int(i) for i in input().split()]
k = a[1]//a[2] - (a[0] - 1)//a[2]
r = a[1]//a[3] - (a[0] - 1)//a[3]
s = a[1]//(int(lcm(a[2],a[3]))) - (a[0] - 1)//int((lcm(a[2],a[3])))
print((a[1] - a[0] + 1 - (k + r - s)))

Solution (Python):

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z
        
A, B, C, D = map(int, input().split())
lcm = int(C * D / gcd(C, D))

num_B_C = B // C
num_B_D = B // D
num_B_CD = B // (lcm)

num_A_C = (A-1) // C
num_A_D = (A-1) // D
num_A_CD = (A-1) // (lcm)

num_all = (num_B_C - num_A_C) + (num_B_D - num_A_D) - (num_B_CD - num_A_CD)
result = (B - (A-1)) - num_all

print(result)

Solution (Python):


import fractions as math

a,b,c,d = map(int,input().split())
cd=c*d//math.gcd(c,d)
tc=((a-1)//c+1)*c
td=((a-1)//d+1)*d
tcd=((a-1)//(cd)+1)*(cd)

ans= (b-a)+1
if c<=b:
    ans-=((b-tc)//c+1)
if d<=b:
    ans-=((b-td)//d+1)
if cd<=b:
    ans+=((b-tcd)//(cd)+1)

print(ans)

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

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

BdivC=B//C
BdivD=B//D
BdivCD=B//(lcm(C,D))
AdivC=(A-1)//C
AdivD=(A-1)//D
AdivCD=(A-1)//(lcm(C,D))

ans=B-(A-1)-(BdivC-AdivC+BdivD-AdivD-BdivCD+AdivCD)

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C, D = MAP()

num_C_yaku = B//C - (A-1)//C  
num_D_yaku = B//D - (A-1)//D  

num_CD_yaku = B//(C*D//int(gcd(C, D))) - (A-1)//(C*D//int(gcd(C, D)))  




print((B-A+1)-(num_C_yaku+num_D_yaku-num_CD_yaku))

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

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

def solve(num, c, d):
  l=lcm(c,d)
  g=gcd(c,d)
  z=l-c//g-d//g+1
  left=(num//l)*l
  ret=(num//l)*z
  ret+=(num-left)-(num-left)//c-(num-left)//d
  return ret

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

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

def mul(head, tail, x):
    length = tail - head + 1
    ans = length // x
    if x - (head % x) <= length % x - 1:
        return ans+1
    return ans

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

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

print(B - A + 1 - (mul(A, B, C) + mul(A, B, D) - mul(A, B, lcm(C, D))))

Solution (Python):
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
    
def lcm(x, y):
    return (x * y) // gcd(x, y)


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

hoge1 = B // C - (A - 1) // C
hoge2 = B // D - (A - 1) // D
hoge3 = B // (C * D) - (A - 1) // (C * D)

saisho = lcm(C, D)
hoge4 = B // saisho - (A - 1) // saisho

print(target - hoge1 - hoge2 + hoge4)

Solution (Python):
import fractions as f
a,b,c,d = map(int,input().split())

e = (c//f.gcd(c,d))*d


if a%c == 0:
    p = b//c - a//c +1
else:
    p = b//c - a//c
if a%d == 0:
    q = b//d - a//d +1
else:
    q = b//d - a//d
if a%e == 0:
    r = b//e - a//e +1
else:
    r = b//e - a//e  

print(b-a+1-p-q+r)

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return int(gcd(b, c))

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

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

l = lcm(C, D)

A = A-1
x = (B-A)
y = (B//C - A//C)
z = (B//D - A//D)
a = (B//l - A//l)
print(x+a - (y+z))

Solution (Python):
def gcd(a,b):
    if b==0:
        return a
    
    return gcd(b,a%b)
  
def lcm(x,y):
    return (x*y) // gcd(x, y)

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

A_C=A//C
if C*A_C!=A:
  A_C+=1
B_C=B//C  
A_D=A//D
if D*A_D!=A:
  A_D+=1
B_D=B//D

E=lcm(C,D)
A_E=A//E
if E*A_E!=A:
  A_E+=1
B_E=B//E

print(B-A+1-(B_C-A_C+1+B_D-A_D+1-(B_E-A_E+1)))

Solution (Python):
def lcm(x, y):
    return (x * y) // gcd(x, y)
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
A,B,C,D=map(int,input().split())
abc=B//C-A//C
abd=B//D-A//D
abcd=(B//(lcm(C,D)))-(A//(lcm(C,D)))
if A%C==0:
    abc+=1
if A%D==0:
    abd+=1
if A%(lcm(C,D))==0:
    abcd+=1





print(B-A+1-(abc+abd-abcd))

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

amount = b - a + 1

if a % c == 0:
  c_bottom = a // c
else:
  c_bottom = a // c + 1
c_top = b // c
num_c = c_top - c_bottom + 1

if a % d == 0:
  d_bottom = a // d
else:
  d_bottom = a // d + 1
d_top = b // d
num_d = d_top - d_bottom + 1

import fractions

e = int(c * d / fractions.gcd(c, d))
if a % e == 0:
  e_bottom = a // e
else:
  e_bottom = a // e + 1
e_top = b // e
num_e = e_top - e_bottom + 1

print(amount - num_c - num_d + num_e)

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

x = c
y = d
while y:
    x, y = y, x % y
gcd = x
lcm = c * d // gcd
if a != b:
    sc = (b // c - (a-1) // c)
    sd = (b // d - (a-1) // d)
    slcm = b // lcm - (a-1) // lcm
    print(b-a+1 - sc - sd + slcm)
else:
    if a % c != 0 and a % d != 0:
        print(1)
    else:
        print(0)