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:
def code_for_A(test=None):

    if test:
        pass
    else:
        S = input()

    continuous = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            continuous += 1

    if continuous > 0:
        answer = 'Bad'
    else:
        answer = 'Good'

    print(answer)


def code_for_B(test=None):

    if test:
        N, L = test
    else:
        N, L = map(int, input().split())

    _sum = int(L * N - N + N * (N + 1) / 2)

    if L <= 0:
        ate = min(0, L + N - 1)
    else:
        ate = max(0, L)

    print(_sum - ate)


def code_for_C(test=None):

    if test:
        A, B, C, D = test
    else:
        A, B, C, D = map(int, input().split())

    def divisible_num(A, B, num):
        result = B // num - (A-1) // num
        return result

    n_C_can_devide = divisible_num(A, B, C)
    n_D_can_devide = divisible_num(A, B, D)

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

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

    n_CD_can_devide = divisible_num(A, B, lcm)

    print(B - A + 1 - n_C_can_devide - n_D_can_devide + n_CD_can_devide)


def main():
    code_for_C()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = [int(v) for v in input().split()]

gcd_cd = fractions.gcd(c, d)
e = c * d // gcd_cd

a_c = a // c
if a % c != 0:
  a_c += 1
b_c = b // c

a_d = a // d
if a % d != 0:
  a_d += 1
b_d = b // d

a_e = a // e
if a % e != 0:
  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) ) )

Submission status: Accepted

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

def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if y == 0:
        return x
    return gcd(y, x%y)

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

L = lcm(C, D)

def interval(l, r, d):
    return (r/d) - (l-1)/d

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

Submission status: Accepted

Solution code:
from fractions import gcd


def count(l, h, div):
    u = h // div
    d = (l - 1) // div
    return u - d


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

Submission status: Accepted

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

from fractions import gcd

def solve(n1,n2):
    k = gcd(n1,n2)
    return int((n1*n2)/k)

l = solve(c,d)


        
ans1 = b - int(b//c) - int(b//d) + int(b//l)
ans2 = a - int(a//c) - int(a//d) + int(a//l)

print(int(ans1-ans2))

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())
cd = lcm(c,d)
n = b-a+1
nc = b//c-(a-1)//c
nd = b//d-(a-1)//d
ncd = b//cd-(a-1)//cd
#print(n,nc,nd,ncd)
print(n-(nc+nd-ncd))

Submission status: Accepted

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

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


lcm_C_D = (C * D) // gcd(C, D)
rem_C = lcm_C_D // C
rem_D = lcm_C_D // D

lcm_count = rem_C + rem_D - 1


rem_A = A % lcm_C_D
if rem_A != 0:
	dif_A = lcm_C_D - rem_A
	count_A_C = dif_A // C
	count_A_D = dif_A // D
	before_count = count_A_C + count_A_D + 1
else:
	before_count = 1
	dif_A = 0



dif_B = B % lcm_C_D
if dif_B != 0:
	count_B_C = dif_B // C
	count_B_D = dif_B // D
	after_count = count_B_C + count_B_D 
else:
	after_count = 0
	


syou_A = (A + dif_A) // lcm_C_D
syou_B = (B - dif_B) // lcm_C_D
between_count = (syou_B - syou_A) * lcm_count


print(B - A + 1 - (after_count + between_count + before_count))

Submission status: Accepted

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

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

def calc(d):
    global a, b
    c1 = (a - 1) // d
    c2 = b // d
    return c2 - c1

lcm = c * d // gcd(c, d)
print(ans - calc(c) - calc(d) + calc(lcm))

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
# print(gcd(a,b))

#最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

cd = lcm(c,d)










n = b-a+1   # ここから，cまたはdで割り切れるものの個数を引く．
# cで割り切れる個数+dで割り切れる個数-c*dで割り切れる個数


if a%c==0:
    c1 = a//c   # 範囲に入っているのは，c*c1から
else:
    c1 = a//c + 1

c2 = b//c       #               c*c2まで．


if a%d==0:
    d1 = a//d
else:
    d1 = a//d + 1

d2 = b//d


if a%(cd)==0:
    cd1 = a//(cd)
else:
    cd1 = a//(cd) + 1

cd2 = b//(cd)



if c1<=c2:
    nc = c2-c1+1
else:
    nc = 0

    
if d1<=d2:
    nd = d2-d1+1
else:
    nd = 0
    

if cd1<=cd2:
    ncd = cd2-cd1+1
else:
    ncd = 0

# print(n,nc,nd,ncd)
print(n-nc-nd+ncd)

Submission status: Accepted

Solution code:
from fractions import gcd

A, B, C, D = map(int, input().split())
# print(A, B, C, D)
CD = C * D // gcd(C, D)
ans1 = B // CD - (A - 1) // CD
ans2 = B // C - (A - 1) // C
ans3 = B // D - (A - 1) // D
print(B - A + 1 - (ans2 + ans3 - ans1))

Submission status: Accepted

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

k = B - A + 1

if A%C == 0:
    sc = B//C -A//C +1
else:
    sc = B//C -A//C

if A%D == 0:
    sd = B//D -A//D +1
else:
    sd = B//D -A//D    
    

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

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

if A%cd == 0:
    scd = B//cd -A//cd +1
else:
    scd = B//cd -A//cd    

print(int(k + scd -sc -sd))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
def input(): return sys.stdin.readline().strip()

# N = int(input())
# L = [int(x) for x in input().split()]
A, B, C, D = map(int, input().split())
# S = input()

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


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


def kosu(n, p):
    return n // p

x = kosu(B, C) - kosu(A - 1, C)
y = kosu(B, D) - kosu(A - 1, D)
z = kosu(B, lcm(C, D)) - kosu(A - 1, lcm(C, D))

print((B - A + 1) - (x + y - z))

Submission status: Accepted

Solution code:
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())
e=b//c
f=b//d
g=(a-1)//c
h=(a-1)//d
k=lcm(c,d)
l=b//k
m=(a-1)//k
cdiv=e+f-g-h-l+m
print(b-a+1-cdiv)

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)

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

Submission status: Accepted

Solution code:
# 最小公倍数を求める
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
a, b, c, d = map(int, input().split())

# cで割り切れるものの数
a_c = a // c if a % c == 0 else a // c + 1
b_c = b // c

ab_c = b_c - a_c + 1

# dで割り切れるものの数
a_d = a // d if a % d == 0 else a // d + 1
b_d = b // d

ab_d = b_d - a_d + 1

# c*dで割り切れるものの数
cd = c * d // gcd(c, d)
a_cd = a // cd if a % cd == 0 else a // cd + 1
b_cd = b // cd

ab_cd = b_cd - a_cd + 1

print(b - a + 1 - ab_c - ab_d + ab_cd)

Submission status: Accepted

Solution code:
# coding=utf-8

A, B, C, D = 4, 9, 2, 3
A, B, C, D = 10, 40, 6, 8
A, B, C, D = 314159265358979323, 846264338327950288, 419716939, 937510582
A, B, C, D = map(int, raw_input().split())


def f(d):
    return B / d - (A - 1) / d


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

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

good = f(C) + f(D) - f(E)
print B - A + 1 - good

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= list(map(int, input().split()))

cd = lcm(C,D)

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

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

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

tgC = max(B//C - (A-1)//C, 0)
tgD = max(B//D - (A-1)//D, 0)
tgCD = max(B//CD - (A-1)//CD, 0)

print((B-A+1)-(tgC+tgD-tgCD))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
import fractions
e=(c*d)//(fractions.gcd(c,d))
cc=b//c-a//c
dd=b//d-a//d
cd=b//e-a//e

if a%c==0:
  cc+=1
if a%d==0:
  dd+=1
if a%e==0:
  cd+=1

print(b-a+1-(cc+dd-cd))

Submission status: Accepted

Solution code:
from fractions import gcd

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

a -= 1
cd = c*d//gcd(c, d)

b_c = b - (b // c + b // d - b // (cd))
a_c = a - (a // c + a // d - a // (cd))
print(b_c- a_c)

Submission status: Accepted

Solution code:
def gcd(a, b): # a < b
    while True:
        c = b%a
        if c == 0:
            break
        b = a
        a = c

    return a


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

start = A // C
end = B // C
if A % C != 0:
    start = start + 1
C_num = end - start + 1

start = A // D
end = B // D
if A % D != 0:
    start = start + 1
D_num = end - start + 1

CD = C * D // gcd(C, D)
start = A // CD
end = B // CD
if A % CD != 0:
    start = start + 1
CD_num = end - start + 1

ans = (B - A + 1) - (C_num + D_num - CD_num)

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

from fractions import gcd


def main():
    # N = int(input())
    A, B, C, D = map(int, input().split())
    length = B - A + 1
    divc = B//C - A//C
    if A % C == 0:
        divc += 1

    divd = B//D - A//D
    if A % D == 0:
        divd += 1
    lcm = C*D//gcd(C, D)
    divcd = B//lcm - A//lcm

    if A % (C*D) == 0:
        divcd += 1
    # print(divc, divd, divcd)

    ans = length - divc - divd + divcd

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import fractions

a1 = a//c
b1 = b//c

r1 = abs(a1-b1)

a2 = a//d
b2 = b//d
r2 = abs(a2-b2)

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

#print(r1)
if a % d == 0:
	r2 += 1
#print(r2)

x = int(c*d/fractions.gcd(c, d))
p = b//x
q = a//x


r = abs(p - q)

if a % x == 0:
	r += 1

#print(r)
print(int((b-a)+1 -(r1 + r2 - r)))

Submission status: Accepted

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

amari_sita1 = A % C
sho_sita1 = A // C
amari_sita2 = A % D
sho_sita2 = A // D
amari_ue1 = B % C
sho_ue1 = B // C
amari_ue2 = B % D
sho_ue2 = B // D

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
kobaisu = lcm(C,D)
amari_sita3 = A % kobaisu
sho_sita3 = A // kobaisu
amari_ue3 = B % kobaisu
sho_ue3 = B // kobaisu

CD_warikirerukosu = sho_ue3 - sho_sita3
if amari_sita3 == 0:
    CD_warikirerukosu +=1

C_warikirerukosu = sho_ue1 - sho_sita1
if amari_sita1 == 0:
   C_warikirerukosu +=1

D_warikirerukosu = sho_ue2 - sho_sita2
if amari_sita2 == 0:
    D_warikirerukosu +=1


print(kosu - (C_warikirerukosu + D_warikirerukosu) + CD_warikirerukosu)

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
lcmCD = C*D//fractions.gcd(C,D)
ac = (A-1)//C
ad = (A-1)//D
bc = B//C
bd = B//D
acd = (A-1)//(lcmCD)
bcd = B//(lcmCD)
print(B-A+1-(bc+bd-bcd-(ac+ad-acd)))

Submission status: Accepted

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

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

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
def lcm(a, b):
	return a * b // gcd (a, b)

lcm_cd = lcm(C, D)



b_mul_c = B // C
b_mul_d = B // D
b_mul_cd = B // lcm_cd

a_mul_c = (A - 1) // C
a_mul_d = (A - 1) // D
a_mul_cd = (A - 1) // lcm_cd

num_b = B - (b_mul_c + b_mul_d - b_mul_cd)
num_a = (A - 1) - (a_mul_c + a_mul_d - a_mul_cd)

print(num_b - num_a)

Submission status: Accepted

Solution code:
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=[int(i) for i in input().split()]
A=A-1
CD=lcm(C,D)
AC=A//C;BC=B//C
AD=A//D;BD=B//D
ACD=A//CD;BCD=B//CD
#print(AC,BC,AD,BD,ACD,BCD)
print(B-A-(BC-AC+BD-AD-(BCD-ACD)))

Submission status: Accepted

Solution code:
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(x, y):
    ans = (x * y) // gcd(x, y)
    return ans

l_c = (a-1)//c
l_d = (a-1)//d
l_c_d = (a-1)//lcm(c, d)

l_ans = a - 1 - (l_c + l_d - l_c_d)


g_c = b//c
g_d = b//d
g_c_d = b//lcm(c, d)
g_ans = b - (g_c + g_d - g_c_d)

print(g_ans - l_ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque


from fractions import gcd

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
    
def lcm(x, y):
    return (x * y) // gcd(x, y)

def main():
    a,b,c,d = LI()
    c_d_gcd = lcm(c,d)
    s = b//c + b//d - b//c_d_gcd
    t = (a-1) // c + (a-1) // d - (a-1) // c_d_gcd
    print(b - a + 1 - (s-t))
main()

Submission status: Accepted

Solution code:
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())

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

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

Submission status: Accepted

Solution code:
# import numpy as np
import fractions

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

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

def undivided_under(N, C, D):
    dived_C = N // C
    dived_D = N // D
    dived_lcm = N // lcm(C, D)

    # print(dived_C, dived_D, dived_lcm)

    return(N - dived_C - dived_D + dived_lcm)

# print(A,B,C,D)
# print(undivided_under( B, C, D ))
# print(undivided_under( A-1, C, D ))

print( int( undivided_under(B, C, D) - undivided_under(A-1, C, D)) )

Submission status: Accepted

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

a,b,c,d=map(int,input().split())
n=b-a+1
lcm=(c*d)//gcd(c,d)
a1=(a-1)//c
b1=b//c
a2=(a-1)//d
b2=b//d
a3=(a-1)//lcm
b3=b//lcm
res=n-b1+a1-b2+a2+b3-a3
print(res)

Submission status: Accepted

Solution code:
import fractions

def calc(v):
    ta = v // C
    tb = v // D
    tc = v // ((C * D) // fractions.gcd(C, D))
    return v-(ta+tb-tc)


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

count = 0
i = A
a = calc(A-1)
b = calc(B)
print(abs(a-b))

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())
e = lcm(c, d)
x = a if (a % c) == 0 else a-(a % c)+c
y = a if (a % d) == 0 else a-(a % d)+d
z = a if (a % e) == 0 else a-(a % e)+e
ans = b-a+1
if x <= b:
    ans -= (b-x)//c+1
if y <= b:
    ans -= (b-y)//d+1
if z <= b:
    ans += (b-z)//e+1
print(ans)

Submission status: Accepted

Solution code:
#最大公約数
def gcd(a, b):
  if a < b:
    a, b = b, a
  if b == 0:
    return a
  c = a % b
  return gcd(b, c)

#最小公倍数
def lcm(a, b):
  return int(a * b / gcd(a, b))

def calc(a, c, d):
  g = lcm(c, d)
  return a - (a // c) - (a // d) + (a // g)
  
A, B, C, D = map(int, input().split())

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

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

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

a,b,c,d = map(int,input().split())
lcm = int(c*d/gcd(c,d))
def num(x):
    return(b//x-(a-1)//x)
ans = (b-a+1)-num(c)-num(d)+num(lcm)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import fractions

def main():
    # a = sys.stdin.readline().strip()
    a, b, c, d = [int(i) for i in sys.stdin.readline().strip().split()]
    # [[int(i) for i in sys.stdin.readline().strip().split()] for _ in range(2)]
    n = b - a + 1
    # print(n)
    if a % c == 0:
        mi_c = a // c
    else:
        mi_c = a // c + 1
    ma_c = b // c
    n -= (ma_c - mi_c + 1)
    # print(ma_c, mi_c, n)

    if a % d == 0:
        mi_d = a // d
    else:
        mi_d = a // d + 1
    ma_d = b // d
    n -= (ma_d - mi_d + 1)
    # print(ma_d, mi_d, n)

    cd = (c * d) // fractions.gcd(c, d)
    if a % cd == 0:
        mi_cd = a // cd
    else:
        mi_cd = a // cd + 1
    ma_cd = b // cd
    n += (ma_cd - mi_cd + 1)
    # print(ma_cd, mi_cd, n)
    print(n)
    
main()

Submission status: Accepted

Solution code:
from fractions import gcd
from math import ceil
lcm = lambda x, y: x * y // gcd(x, y)
def solve():
    a, b, c, d = map(int, input().split())
    if c == 1 or d == 1:
        return 0
    def f(x):
        return len(range(ceil(a / x) * x, b + 1, x))
    C = f(c)
    if c == d:
        return b - a + 1 - C
    D = f(d)
    cd = lcm(c, d)
    CD = f(cd)
    return b - a + 1 - (C + D - CD)
print(solve())

Submission status: Accepted

Solution code:
import sys
import fractions
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
A, B, C, D = tuple(li())
def helper(A, B, C):
    return (B) // C - (A-1) // C
num1 = helper(A, B, C)
num2 = helper(A, B, D)
num3 = helper(A, B, C * D // fractions.gcd(C, D))
delta = num1 + num2 - num3
print(B - A + 1 - delta)

Submission status: Accepted

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

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

def hoge(n):
    c = n // C
    d = n // D
    cd = n // both
    non=  c + d - cd
    return n - non

up = hoge(B)
down  = hoge(A - 1)

ret = up - down
print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

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


def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x


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


def f(a, b, c):
    if a % c == 0:
        a1 = a // c
    else:
        a1 = a // c + 1
    b1 = b // c
    r = b1 - a1 + 1
    return r


# c = (B - A + 1) // C
# d = (B - A + 1) // D
# cd = (B - A + 1) // (C * D)

c = f(A, B, C)
d = f(A, B, D)
cd = f(A, B, lcm(C, D))

n = B - A + 1
print(n - c - d + cd)

Submission status: Accepted

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

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

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

def get_b_cnt(a,b,x):
    res = 0
    N = b - a + 1
    x1 = a % x 
    if x1 > 0:
        x1 = x - x1

    if x1 < N:
        res += 1

    N2 = N - x1 -1

    if N2 > 0:
        res += (N2 // x)

    return res


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

    print(B-A+1-(get_b_cnt(A,B,C)+get_b_cnt(A,B,D)-get_b_cnt(A,B,E)))

    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(a, b):
    if a<b: a, b = b, a
    while a%b:
        a, b = b, a%b
    return b

def main():
    a, b, c, d = map(int, input().split())
    ans = b - a + 1
    if a%c: ans -= b//c-a//c
    else: ans -= b//c+1-a//c

    if a%d: ans -= b//d-a//d
    else: ans -= b//d+1-a//d

    sks = (c*d) // gcd(c, d)
    if a%sks: ans += b//sks-a//sks
    else: ans += b//sks+1-a//sks
    print(ans)

if __name__=="__main__": main()

Submission status: Accepted

Solution code:
import math
A,B,C,D = input().split()
A = int(A)
B = int(B)
C = int(C)
D = int(D)
a = C
b = D
while a % b != 0:
    a, b = b, a % b
g = C*D//b
a1 = A-1
a2 = B
ans1= (a1//C+a1//D-a1//g)
ans2= (a2//C+a2//D-a2//g)
print(B-A+1-ans2+ans1)

Submission status: Accepted

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

cnt = 0
from fractions import gcd


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


c = B // C
c2 = A // C
if A % C == 0:
    c2 -= 1
d = B // D
d2 = A // D
if A % D == 0:
    d2 -= 1
t = B // lcm(C, D)
t2 = A // lcm(C, D)
if A % lcm(C, D) == 0:
    t2 -= 1

print(B - A + 1 - ((c - c2) + (d - d2) - (t - t2)))
# for i in range(A, B + 1):
#     if i % C != 0 and i % D != 0:
#         continue
#     else:
#         print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import fractions
# input
a, b, c, d = map(int, input().split())
f = c*d//(fractions.gcd(c, d))
# calc
# cでわり切れる数
ac = (a-1)//c
bc = b//c
# dで割り切れる数
ad = (a-1)//d
bd = b//d
# かぶり
af = (a-1)//f
bf = b//f
# output
print((b-a+1)-((bc-ac)+(bd-ad)-(bf-af)))

Submission status: Accepted

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

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

CD = int(C*D/gcd(C,D))

BokC = B//C
BokD = B//D
BokCD = B//CD
Bika = B - (BokC+BokD-BokCD)

AokC = (A-1)//C
AokD = (A-1)//D
AokCD = (A-1)//CD
Amiman = (A-1) - (AokC+AokD-AokCD)
print(int(Bika-Amiman))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''Snippets for lcm.
Available functions:
- lcm: Compute least common multiple of a and b.
'''


def lcm(a: int, b: int) -> int:
    '''Compute least common multiple of a and b.
    Args:
        a: Int of number (greater than 0).
        b: Int of number (greater than 0).
    Returns:
        least common multiple.
    Landau notation: O(log n)
    See:
    https://gist.github.com/endolith/114336/eff2dc13535f139d0d6a2db68597fad2826b53c3
    https://docs.python.org/3/library/sys.html#sys.version_info
    '''

    from sys import version_info

    if version_info.major == 3 and version_info.minor >= 5:
        from math import gcd
    else:
        from fractions import gcd

    return a * b // gcd(a, b)


def main():
    a, b, c, d = map(int, input().split())
    l = lcm(c, d)
    x = b // c - (a - 1) // c
    y = b // d - (a - 1) // d
    z = b // l - (a - 1) // l
    w = b - a + 1

    if c % d == 0 or d % c == 0:
        print(w - x)
    else:
        print(w - (x + y - z))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == "__main__":
    A,B,C,D = map(int,input().split())
    ac = A%C
    E = int(C*D/gcd(C,D))
    if ac == 0:
        modc = B//C - A//C + 1
    else:
        modc = B//C - A//C
    ad = A%D
    if ad == 0:
        modd = B//D - A//D + 1
    else:
        modd = B//D - A//D
    ae = A%E
    if ae == 0:
        mode = B//E - A//E + 1
    else:
        mode = B//E - A//E
    print(int(B-A+1-modc-modd+mode))

Submission status: Accepted

Solution code:
def gcd(x,y):
	if x%y == 0:
		return y
	else:
		return gcd(y,x%y)
A,B,C,D = map(int, raw_input().split())
A = A-1
g = C*D/gcd(C,D)
data = [A/C,A/D,B/C,B/D,A/g,B/g]
print((B-A)-(data[2]+data[3]+data[4]-data[0]-data[1]-data[5]))

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

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

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)

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())

cc = b // c - (a-1) // c
dd = b // d - (a-1) // d
l = lcm(c, d)
cd = b // l - (a-1) // l

print(b-a+1-(cc+dd-cd))

Submission status: Accepted

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


A, B, C, D = map(int, input().split())
if C == 1 or D == 1:
    print(0)
else:
    an1 = B//C
    an2 = (A - 1)//C
    an3 = B//D
    an4 = (A - 1)//D
    an5 = B//(C*D//gcd(C,D))
    an6 = (A - 1)//(C*D//gcd(C,D))
    print(B - A + 1 - (an1-an2+an3-an4-(an5-an6)))

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = (int(x) for x in input().split())
l = C*D//fractions.gcd(C,D)
comp = (B//C - (A-1)//C) + (B//D - (A-1)//D) - (B//l - (A-1)//l)
print(B-A+1-comp)

Submission status: Accepted

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

numC = B//C - (A-1)//C
numD = B//D - (A-1)//D

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

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

numCD = B//CD - (A-1)//CD
numAll = B - A + 1
print(numAll - numC - numD + numCD)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
cd = c*d//fractions.gcd(c,d)
e = a-1
f = (b//c + b//d - b//(cd)) - (e//c + e//d - e//(cd))
print(b-e-f)

Submission status: Accepted

Solution code:
a, b, n, m = [int(i) for i in input().split()]

def gcd(p,q):
  while q!=0:
    p,q=q,p%q
  return p

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

nm = lcm(n, m)

def count(k):
    min_cand = a // k if a % k == 0 else a // k + 1
    if b < min_cand * k:
        return 0
    max_cand = b //k
    if max_cand * k < a:
        return 0

    return max_cand - min_cand + 1

size = count(n) + count(m) - count(nm)

print(b - a + 1 - size)

Submission status: Accepted

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


s = int(C * D // gcd(C, D))

p  = B - A + 1 - int((B // C - (A - 1) // C) + (B // D - (A - 1) // D) - (B // s - (A - 1) // s))
print(p)

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())

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

temp = int(lcm(c,d))

ans = ans+(b//temp-a//temp)


if a%c == 0:
    ans -= 1
    
if a%d == 0:
    ans -= 1
    
if a%(c*d) == 0:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import fractions 
a,b,c,d=map(int,input().split())
cd=fractions.gcd(c,d)
lcm=c*d//cd
bac=b//c-a//c
bad=b//d-a//d
balcm=b//lcm-a//lcm
if a%c==0:
    bac+=1
if a%d==0:
    bad+=1
if a%lcm==0:
    balcm+=1
print(b-a+1-(bac+bad-balcm))

Submission status: Accepted

Solution code:
# coding: utf-8
from sys import stdin
import sys, fractions
import numpy as np

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


a,b,c,d = [int(x) for x in stdin.readline().rstrip().split()]
#print(a, b, c, d)
#bまでで3で割り切れる数
three_all = b // c
#a-1までで3で割り切れる数
three_less = (a-1) // c
three_range = three_all - three_less
    
two_all = b // d
two_less = (a-1) // d
two_range = two_all - two_less
    
z = lcm(c,d)
six_all = b // z
six_less = (a-1) // z
six_range = six_all - six_less
    
num = three_range + two_range - six_range
    
ans = b-a+1-num
print(ans)

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
def lcm(a, b):
	return a * b // gcd (a, b)
def ans(i):
    return i - (i//C + i//D - i//lcm(C,D))

print(ans(B)-ans(A-1))

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())
cd = lcm(c, d)
res = (b-a+1) - ((b//c - (a-1)//c) + (b//d - (a-1)//d) - (b//cd - (a-1)//cd))
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

from fractions import gcd

a, b, c, d = map(int,input().split())
a = a-1
dc = b//c
dc -= a//c

dd = b//d
dd -= a//d

lcm = c*d//gcd(c,d)
dcd = b//lcm
dcd -= a//lcm

ans = b-a-dc-dd+dcd

print(ans)

Submission status: Accepted

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

lcm_cd = C * D // fractions.gcd(C, D)
divBbyC = B // C
divBbyD = B // D
divBbyCD = B // lcm_cd
divAmbyC = (A - 1) // C
divAmbyD = (A - 1) // D
divAmbyCD = (A - 1) // lcm_cd

ans = (B - divBbyC - divBbyD + divBbyCD) - ((A - 1) - divAmbyC - divAmbyD + divAmbyCD)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

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

def anti_division_iter(a, b, r):
    n = b // r
    m = (a-1) // r
    return n - m

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

div_c = anti_division_iter(a, b, c)
div_d = anti_division_iter(a, b, d)
div_cd = anti_division_iter(a, b, lcm(c, d))

print((b-a+1) - (div_c + div_d - div_cd))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
lcm=int(c*d/gcd(c,d))
#1~Nに何個kの倍数があるか
def counter(n):
    return n-(n//c + n//d - n//lcm)
countA=counter(a-1)
countB=counter(b)
#print(countA,countB)
print(-countA+countB)

Submission status: Accepted

Solution code:
from fractions import gcd

def debug(*args):
    import sys
    #print(*args, file=sys.stderr)

def solve(A, B, C, D):
    L = C * D // gcd(C, D)
    A-=1
    debug("A=%d, B=%d, C=%d, D=%d" %(A,B,C,D))
    debug((B//C, A//C), (B//D, A//D) , (B//L , A//L))
    debug((B//C - A//C), (B//D - A//D) , (B//L - A//L))
    return B-A- ((B//C - A//C) + (B//D - A//D) - (B//L - A//L))

def main():
    A, B, C, D = [int(x) for x in input().split()]
    print(solve(A, B, C, D))
    pass

main()

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
def divnum(A, B, X):
    return B//X - (A-1)//X
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)
print((B - A + 1) - divnum(A, B, C) - divnum(A, B, D) + divnum(A, B, lcm(C,D)))