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:
a, b, c, d = map(int, input().split())

from fractions import gcd

def f(i, l, r):
  return r//i - (l-1)//i

cnt = f(c, a, b) + f(d, a, b) - f((c*d)//gcd(c, d), a, b)

print(b - a + 1 - cnt)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())
A = A-1
f=fractions.gcd(C,D)
f2=C*D//f

Aans = A - (A//C + A//D - A//f2)
Bans = B - (B//C + B//D - B//f2)
print(Bans- Aans)

Submission status: Accepted

Solution code:
import fractions

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

X = (C * D) // fractions.gcd(C, D)
ans = (B - A + 1)\
      - (B // C - A // C)\
      - (B // D - A // D)\
      + (B // X - A // X)
if A % C == 0:
      ans -= 1
if A % D == 0:
      ans -= 1
if A % X == 0:
      ans += 1

print(ans)

Submission status: Accepted

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

def andiv(M,N):
    return((N//M) * (M-1) + N%M)

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 = andiv(C,B) + andiv(D,B) - andiv(lcm(C,D),B)
F = andiv(C,A-1) + andiv(D,A-1) - andiv(lcm(C,D),A-1)

print(int(E-F))

Submission status: Accepted

Solution code:
import fractions

def lcm(a,b):
    res = a*b // fractions.gcd(a,b)
    return res
def f(x,y,z):
    res = x
    res -= x//y
    res -= x//z
    res += x//lcm(y,z)
    return res


A, B, C, D = map(int, input().split())
ans1 = f(B,C,D)
ans2 = f(A-1,C,D)
ans = ans1 - ans2
print(int(ans))

Submission status: Accepted

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

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

c_multiple_last = b // c
d_multiple_last = b // d
cd_multiple_last = b // lcm(c, d)

c_multiple_first = (a-1) // c
d_multiple_first = (a-1) // d
cd_multiple_first = (a-1) // lcm(c, d)

c_count = c_multiple_last - c_multiple_first
d_count = d_multiple_last - d_multiple_first
cd_count = cd_multiple_last - cd_multiple_first

a_to_b_count = b - a + 1
ans = a_to_b_count - (c_count + d_count - cd_count)
print(ans)

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())
li=[]
gc = lcm(c,d)
for i in [a-1,b]:
    bc = i//c
    bd = i//d
    cd = i//gc
    li.append(i-(bc+bd-cd))
print(int(li[1]-li[0]))

Submission status: Accepted

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b, c, d = list(map(int, input().rstrip('\n').split()))
    cd = b // c - (a - 1) // c
    dd = b // d - (a - 1) // d
    gcd = c * d // fractions.gcd(c, d)
    gcdd = b // gcd - (a - 1) // gcd
    print(b - a + 1 - cd - dd + gcdd)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
from fractions import gcd 
import sys

l, r, c, d = map(int, sys.stdin.readline().split())

count = 0

first = (l + c - 1)//c 
last = r//c 

count += last - first + 1

first = (l + d - 1)//d 
last = r//d 
count += last - first + 1

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

first = (l + lcm - 1)//lcm 
last = r // lcm
count -= last - first + 1


print(r - l - count + 1)

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
def lcm(a,b):
    return a*b//gcd(a,b)
cd = lcm(c,d)
print(int((b-a+1)-(b//c+b//d-(a-1)//c-(a-1)//d)+(b//(cd)-(a-1)//(cd))))

Submission status: Accepted

Solution code:
import fractions

A,B,C,D =map(int,input().split())
c_i =  ((A+C-1)//C)
c_f = B//C
c_dis = c_f-c_i+1 if c_f-c_i >= 0 else 0

d_i = ((A+D-1)//D)
d_f = B//D
d_dis = d_f-d_i+1 if d_f-d_i>= 0 else 0

cd = C*D//fractions.gcd(C,D)
cd_i = ((A+cd-1)//cd)
cd_f = B//cd
cd_dis = cd_f-cd_i+1 if cd_f-cd_i >= 0 else 0

ans = B-A+1 - c_dis - d_dis+ cd_dis

print(ans)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def kosuu(a,b,c):
    if a%c==0:
        return (b-a)//c+1
    else:
        return(b-(a+(c-a%c)))//c+1

g=0
c1=c
d1=d
while c1!=0 and d1!=0:
    if c1<=d1:
        d1=d1%c1
    else:
        c1=c1%d1
if c1!=0:
    g=c1
else:
    g=d1

print(b-a+1-kosuu(a,b,c)-kosuu(a,b,d)+kosuu(a,b,c*d//g))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def kosuu(a,b,c):
    if a%c==0:
        return (b-a)//c+1
    else:
        return(b-(a+(c-a%c)))//c+1

l=0
c1=c
d1=d
while c1!=0 and d1!=0:
    if c1<=d1:
        d1=d1%c1
    else:
        c1=c1%d1
if c1!=0:
    l=c1
else:
    l=d1

print(b-a+1-kosuu(a,b,c)-kosuu(a,b,d)+kosuu(a,b,c*d//l))

Submission status: Accepted

Solution code:
import fractions
m = list(map(int,input().split()))
c=[]
c.append(m[2])
c.append(m[3])
f=fractions.gcd(m[3],m[2])
p=(m[3]*m[2])// f
c.append(p)
         
a=[]
a.append(m[0]-1)
a.append(m[1])

d=[]
for i in range(3):
    for j in range(2):
        d.append(a[j]//c[i])
        
x = m[0]-1 - d[0]-d[2]+d[4]
y = m[1] - d[1]-d[3]+d[5]
print(int(y-x))

Submission status: Accepted

Solution code:
from fractions import gcd

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


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


def cantdiv(x):
    return x - x // c - x // d + x // lcm(c, d)


print(cantdiv(b) - cantdiv(a - 1))

Submission status: Accepted

Solution code:
L = list(map(int, input().split()))

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

def count_between(x, a, b):
    c = x
    l = (a * b) // gcd(a, b)
    c = c - x // a - x // b + x // l
    return c


print(count_between(L[1], L[2], L[3]) - count_between(L[0] - 1, L[2], L[3]))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################
from fractions import gcd

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


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

A -= 1

# a/b以下の条件を満たす数
nb = B - B//C - B//D + B//lcm(C, D)
na = A - A//C - A//D + A//lcm(C, D)

print(nb - na)

Submission status: Accepted

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

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

b_ans = b - (b//c + b//d - b//lcm)
a_ans = a - (a//c + a//d - a//lcm)

print(b_ans - a_ans)

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int,input().split())
e = c*d//fractions.gcd(c,d)
l = [c,d,e]
l2 = [0,0,0]
for i in range(0,3):
    if a%l[i] == 0:
        l2[i] = b//l[i] - a//l[i] +1
    else:
        l2[i] = b//l[i] - a//l[i]
print(b-a+1 -l2[0] -l2[1] + l2[2])

Submission status: Accepted

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

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

mc = b // c - (a-1) // c
md = b // d - (a-1) // d
mcd = b // (c*d//gcd(c, d)) - (a-1) // (c*d//gcd(c, d))

print(int((b - a + 1) - mc - md + mcd))

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

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
import fractions
G = (C*D)//fractions.gcd(C, D)
print(B - A + 1 - ( B//C - (A-1)//C + B//D - (A-1)//D - B//G + (A-1)//G ))

Submission status: Accepted

Solution code:
def gcd_base(x,y):
    while y!=0:
        x,y = y,x%y
    return x

def lcm_base(x,y):
    return (x * y) // gcd_base(x,y)

a,b,c,d = map(int,input().split())
ctmp = b//c - (a-1)//c
dtmp = b//d - (a-1)//d
lcm_cd = lcm_base(c,d)
cdtmp = b//lcm_cd - (a-1)//lcm_cd
ans = (b - a + 1) - (ctmp + dtmp - cdtmp)
print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
from _operator import itemgetter
from collections import Counter
from fractions import gcd
from math import log2, pi, ceil

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

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

a, b, c, d = na()
x1 = a // c
y1 = a // d
z1 = a // (lcm(c, d))

x2 = b // c
y2 = b // d
z2 = b // (lcm(c, d))

ans = b - (x2 + y2 - z2)  - (a - (x1 + y1 - z1))
if a % c != 0 and a % d != 0:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
p=c
q=d
e=b//c-(a-1)//c
f=b//d-(a-1)//d
while c%d!=0 and d%c!=0:
    if c>d:
        c=c-d
    elif c<=d:
        d=d-c
if c>d:
    gcm=d
else:
    gcm=c
lcm=(p*q)//gcm
g=b//lcm-(a-1)//lcm
ans=b-a+1-e-f+g
print(int(ans))

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

def main():
  a,b,c,d=LI()
  ans=b-a+1
  ans-=b//c+(-a//c)+1
  ans-=b//d+(-a//d)+1
  ans+=b//int(lcm(c,d))+(-a//int(lcm(c,d)))+1
  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
def find_saidaikouyakusu(n1,n2):#a,bの最大公約数を求める
    shou = n1//n2
    amari = n1%n2
    if amari == 0:
        return n2
    else:
        return find_saidaikouyakusu(n2,amari)



def find_saishoukoubaisu(n1,n2):
    return (n1*n2)//find_saidaikouyakusu(n1,n2) 



a,b,c,d = map(int,input().split())
s = find_saishoukoubaisu(d,c)
ans = (b-a+1) - ((b//c - (a-1)//c) + (b//d - (a-1)//d) - (b//s - (a-1)//s))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf8 -*-
import fractions

a,b,c,d = map(int, input().split())
t = b - a + 1
dc = (b // c) - (a // c) if a % c != 0 else (b // c) - (a // c) + 1
dd = (b // d) - (a // d) if a % d != 0 else (b // d) - (a // d) + 1
lc = c * d // fractions.gcd(c, d)
dlc = (b // lc) - (a // lc) if a % lc != 0 else (b // lc) - (a // lc) + 1
ans = t - dc - dd + dlc
print(ans)

Submission status: Accepted

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

f1=fractions.gcd(c,d)
f2=c*d//f1

a=a-1
aa=a-a//c-a//d+a//f2
bb=b-b//c-b//d+b//f2

print(bb-aa)

Submission status: Accepted

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

all_pattern = B - (A - 1)
mul_c = B // C - (A - 1) // C
mul_d = B // D - (A - 1) // D
l = C * D // fractions.gcd(C, D)
mul_gcd = B // l - (A - 1) // l

res = all_pattern - mul_c - mul_d + mul_gcd
print(res)

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())
r = 0
bc = b // c
bd = b // d
bcd = b // lcm(c, d)
ac = -(-a // c)
ad = -(-a // d)
acd = -(-a // lcm(c, d))
print(b - a + 1 - bc + ac - 1 - bd + ad - 1 + bcd - acd + 1)

Submission status: Accepted

Solution code:
import fractions

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

    c_cnt = (B // C) - ((A-1) // C)
    d_cnt = (B // D) - ((A-1) // D)

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

    cd_cnt = (B // lcm) - ((A-1) // lcm)

    print(B - (A-1) - c_cnt - d_cnt + cd_cnt)


    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

divc=(b//c) - ((a-1)//c)
divd=(b//d) - ((a-1)//d)
divcd=(b//lcm) - ((a-1)//lcm)
print((b-a+1)-(divc+divd-divcd))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
A,B,C,D=map(int, input().split())
f=C
g=D
while f%g!=0:
  f,g=[g, f%g]
l=C*D//g
m=B//l
n=(A-1)//l
print(B-(B//C)-(B//D)+m-(A-1-((A-1)//C)-((A-1)//D)+n))

Submission status: Accepted

Solution code:

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 nb_divisers(n,m):
    return n//m
def nb_d_btw(f,g,n):
    if f%n==0:
        return nb_divisers(g,n)-nb_divisers(f,n)+1
    else:
        return nb_divisers(g,n)-nb_divisers(f,n)
def nb_notdivisers_f(a,b,c,d):
    e=int(c*d/gcd(c,d))
    return b-a+1-(nb_d_btw(a,b,c)+nb_d_btw(a,b,d)-nb_d_btw(a,b,e))
print(nb_notdivisers_f(A,B,C,D))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import fractions
a, b, c, d = map(int, input().split())

# cとdの最小公倍数
cd = int((c*d)/fractions.gcd(c, d))
# a未満で条件を満たす整数の個数
cnt_a = a-1
# b以下で条件を満たす整数の個数
cnt_b = b

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

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

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

Submission status: Accepted

Solution code:
def lcm(a,b):
    x,y=a,b
    while b:
        a,b=b,a%b
    return x*y//a
X=[]
A=list(map(int, input().split()))
A.append(lcm(A[2],A[3]))
for i in range(3):
    if A[0]%A[i+2]==0:
        X.append(int(A[1]//A[i+2])-int(A[0]//A[i+2])+1)
    else:
        X.append(int(A[1]//A[i+2])-int(A[0]//A[i+2]))
print(A[1]-A[0]+1-X[0]-X[1]+X[2])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
from fractions import gcd

def f(a, x):
    """1以上a以下で、xで割り切れるものの数"""
    return a // x

def lcm(a, b):
    """ aとbの最小公倍数を返す """
    return a*b // gcd(a, b)

def solve():
    A, B, C, D = list(map(int, sys.stdin.readline().split()))
    A -= 1

    # CでもDでも割り切れないもの
    b = B - f(B, C) - f(B, D) + f(B, lcm(C, D))
    a = A - f(A, C) - f(A, D) + f(A, lcm(C, D))
    print(b-a)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y = y,x
    while y>0:
        x,y = y,x%y
    return x
A,B,C,D = map(int,input().split())
c1 = B//C
d1 = B//D
CD = C*D//gcd(C,D)
cd1 = B//CD
c2 = (A-1)//C
d2 = (A-1)//D
cd2 = (A-1)//CD
b = B-(c1+d1-cd1)
a = A-1-(c2+d2-cd2)
print(b-a)

Submission status: Accepted

Solution code:
A = list(map(int, input().split()))
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

count_c = 0
count_d = 0
count_cd = 0
cd = lcm(A[2], A[3])
count_c = A[1] // A[2] - (A[0]-1) // A[2]
count_d = A[1] // A[3] - (A[0]-1) // A[3]
count_cd= A[1] // cd - (A[0]-1) // cd

print(A[1] - A[0] + 1 - (count_c + count_d - count_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 

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

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

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int, input().split())
gcd = fractions.gcd(c,d)
lcm = c * d // gcd
num = [c,d,lcm]
l = b - a + 1
temp = []

for i in range(3):
  count = 0
  if l - num[i] >= 0:
    count += l // num[i]
    if l % num[i] != 0:
      if b % num[i] < (b - (l % num[i]) + 1) % num[i]:
        count += 1
  else:
    if b % num[i] < l:
        count += 1
  temp.append(count)

ans = l - (temp[0] + temp[1] - temp[2])
print(ans)

Submission status: Accepted

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


divc = b//c-(a-1)//c
divd = b//d-(a-1)//d

def gcd(s,t):
    while s%t!=0:
        tmp1 = s//t
        tmp2 = t
        t = s-tmp1*t
        s = tmp2
        #print(s,t)
    return t
g = gcd(c,d)
#print(g)
l = c*d//g
#print(l)
divl = b//l-(a-1)//l

ans = b-a+1 -divc-divd + divl

print(ans)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = [int(i) for i in input().split()]
e = b - a + 1
lcm = c*d//fractions.gcd(c,d)

bc = b//c
bd = b//d
ac = (a-1)//c
ad = (a-1)//d
bcd = b//lcm
acd = (a-1)//lcm

f = (bc + bd - bcd) - (ac+ ad -acd)

print(e-f)

Submission status: Accepted

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

import math

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

mul_c = b // c - (a - 1) // c
mul_d = b // d - (a - 1) // d

gcd_c_d = gcd(c, d)
lcm_c_d = gcd_c_d * (c // gcd_c_d) * (d // gcd_c_d)
mul_c_d = b // lcm_c_d - (a - 1) // lcm_c_d

print(b - a + 1 - (mul_c + mul_d - mul_c_d))

Submission status: Accepted

Solution code:
#考え方
#（BについてCでもDでも割り切れない数の個数）-（についてCでもDでも割り切れない数の個数）
#↑それぞれは、B -（B//C + B//D - B//lcm(C,D)) 、　A -（A//C + A//D - A//lcm(C,D))で出せる

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

    else:
        return gcd(y,x%y)



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

if C < D:
    t = C
    C = D
    D = t

max_ky = gcd(C,D)

#最小公倍数
lcm_c = C//max_ky
lcm_d = D//max_ky
lcm = max_ky * lcm_c * lcm_d

count_b = B - (B//C + B//D - B//lcm)
count_a = A - (A//C + A//D - A//lcm)
if(A%C != 0 and A%D != 0):
    count_a -= 1
ans = count_b - count_a

print(ans)






#りゅうせいの解答1 実行時間超過
#A, B, C, D = map(int,input().split())
# ans = 0
# j = A
# while j <= B:
#     count = 0
#     if j%C:
#         count += 1
#     if j%D:
#         count += 1
#
#     if count == 2:
#         ans += 1
#
#     j+= 1
#
# print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = list(map(int,input().split()))
l = (C*D)//fractions.gcd(C,D)
a = [(A-1)//C,(A-1)//D,(A-1)//l]
#print(a)
b = [B//C,B//D,B//l]
#print(b)
c = [b[0]-a[0],b[1]-a[1],b[2]-a[2]]
print(B-A+1-c[0]-c[1]+c[2])

Submission status: Accepted

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

print((b-a+1) - (b//c - (a-1)//c) - (b//d - (a-1)//d) + (b//e - (a-1)//e))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d=map(int,input().split())
lenth=b-a+1

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

def divnumber(c):
	ans=lenth//c
	rem1=a%c
	if rem1==0:rem1+=c
	rem2=lenth%c-1
	if rem1+rem2>=c:
		ans+=1
	return ans

print(lenth-divnumber(c)-divnumber(d)+divnumber(lcm(c,d)))

Submission status: Accepted

Solution code:
from fractions import gcd

def calcAns(n,x,y):
    return n - ((n//x) + (n//y) - (n//((x*y)//gcd(x,y))))

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

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
E = C * D // gcd(C, D)
def cnt(C):
  return B // C - (A - 1) // C
print(B - A + 1 - cnt(C) - cnt(D) + cnt(E))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int, input().split())
cnt=0
num_c = b//c - (a-1)//c
num_d = b//d - (a-1)//d
num_c_d = b//((c*d)//fractions.gcd(c,d))- (a-1)//((c*d)//fractions.gcd(c,d))
total = num_c + num_d - num_c_d
print(int((b-a+1) - total))

Submission status: Accepted

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

print(int(num_divb)-int(num_diva))

Submission status: Accepted

Solution code:
import fractions

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

def get_muls(n):
    return (b // n) - ((a - 1) // n)

res = b - (a - 1) - get_muls(c) - get_muls(d) + get_muls(c * d // fractions.gcd(c, d))
print(res)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a, b, c, d = map(int, 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 ans(num, x, y):
    return num - (num // x + num // y - num // lcm(x, y))

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

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
C=b//c
D=b//d
import fractions
CD=b//(c*d//(fractions.gcd(c,d)))
B=b-C-D+CD
C_=(a-1)//c
D_=(a-1)//d
C_D_=(a-1)//(c*d//(fractions.gcd(c,d)))
A=a-1-C_-D_+C_D_
print(B-A)

Submission status: Accepted

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

B_both = B//(CD)
B_C = B//C
B_D = B//D
first_term = B-(B_C+B_D-B_both)
A -= 1
A_both = A//(CD)
A_C = A//C
A_D = A//D
second_term = A-(A_C+A_D-A_both)

print(first_term-second_term)

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x
import math
A, B, C, D = (int(a) for a in input().split())
lcm = gcd(C, D)
a = B - A + 1
b = abs(B // C - (A - 1) // C)
c = abs(B // D - (A - 1) // D)
d = abs(B // ((C * D) // lcm) - (A - 1) // ((C * D) // lcm))
print(a - (b + c - d))

Submission status: Accepted

Solution code:
import fractions # math.gcdはatcoderでは通らないので注意

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

def lcm(x, y):
    return((x * y) // fractions.gcd(x, y)) # lcmという関数はない(mathでもない)

def f(x, y): # x以下の自然数でyで割り切れる個数
    return(x // y)

def g(x, y, z): # x以上y以下の自然数でzで割り切れる個数
    return(f(y, z) - f(x-1, z))

n = B - A + 1
cn = g(A, B, C)
dn = g(A, B, D)
cdn = g(A, B, lcm(C, D))

ans = n - (cn + dn - cdn)
print(ans)

Submission status: Accepted

Solution code:
import fractions # math.gcdはatcoderでは通らないので注意

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

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

n = B - A + 1
cn = B // C - (A - 1) // C
dn = B // D - (A - 1) // D
cdn = B // lcm(C, D) - (A - 1) // lcm(C, D)

ans = n - (cn + dn - cdn)
print(ans)

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

n = B - A + 1
cn = B // C - (A - 1) // C
dn = B // D - (A - 1) // D
cdn = B // lcm(C, D) - (A - 1) // lcm(C, D)

ans = n - (cn + dn - cdn)
print(ans)

Submission status: Accepted

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

def gcd(c,d):
	if(c==0):
		return d
	else:
		return gcd(d%c,c)
prod = C*D
lcm = prod//gcd(C,D)

A-=1

AC=A//C
AD=A//D
BC=B//C
BD=B//D
ACD=A//lcm
BCD=B//lcm

print(B-A-BC-BD+BCD+AC+AD-ACD)

Submission status: Accepted

Solution code:
import fractions as math

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

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

a_d_c = a // c
b_d_c = b // c

a_d_d = a // d
b_d_d = b // d

a_d_cd = a // cd
b_d_cd = b // cd

b_d = b_d_c + b_d_d - b_d_cd
a_d = a_d_c + a_d_d - a_d_cd

ans =  b - b_d - a + a_d

print(ans)

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split(" "))
def gcd(c,d):
	if(c==0):
		return d
	else:
		return gcd(d%c,c)
prod = c*d
lcm = prod//gcd(c,d)
a1=b//c - (a-1)//c
a2=b//d - (a-1)//d
a3=b//lcm-(a-1)//lcm
print(b-a+1-a1-a2+a3)

Submission status: Accepted

Solution code:
def f_c():
    import fractions
    a, b, c, d = map(int, input().split())
    c_n = b//c-a//c+1 if a%c==0 else b//c-a//c
    d_n = b//d-a//d+1 if a%d==0 else b//d-a//d
    cd = c*d//fractions.gcd(c, d)
    cd_n = b//cd-a//cd+1 if a%cd==0 else b//cd-a//cd
    print(b-a+1-(c_n+d_n-cd_n))

if __name__ == "__main__":
    f_c()

Submission status: Accepted

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

lcm = int(C*D / fractions.gcd(C,D))
ans_b = B - (B // C) - (B // D) + (B // lcm)
ans_a = A - 1 - ((A - 1)// C) - ((A - 1)// D) + ((A - 1) // lcm)

print(ans_b - ans_a)

Submission status: Accepted

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

icm = int(C*D / fractions.gcd(C,D))
ans = (B - A + 1)
if A != B:
    if A % C == 0:
        ans -= int(B // C - A // C) + 1
    else:
        ans -= int(B // C - A // C)
    if A % D == 0:
        ans -= int(B // D - A // D) + 1
    else:
        ans -= int(B // D - A // D)

    if A % icm == 0:
        ans += int(B // icm - A // icm) + 1
    else:
        ans += int(B // icm - A // icm)
    print(int(ans))
else:
    if A % C == 0 or A % D == 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

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

lcm = int(C*D / fractions.gcd(C,D))
ans_b = B - (B // C) - (B // D) + (B // lcm)
ans_a = A - 1 - ((A - 1)// C) - ((A - 1)// D) + ((A - 1) // lcm)

print(int(ans_b - ans_a))

Submission status: Accepted

Solution code:
A, B, C, D, = input().split()
A, B, C, D, = int(A), int(B), int(C), int(D)
def lcm(a,b):
    m = a*b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a+b)
for_D_start = B // D
for_C_start = B // C
sum_start = for_C_start + for_D_start - B // lcm(C,D)
for_C_A = (A-1) // C
for_D_A = (A-1) // D
sum_A = for_C_A + for_D_A - (A-1) // lcm(C,D)
print(B - A + 1 - (sum_start - sum_A))
#print(for_D_A, for_C_A, for_D_start, for_C_start, sum_A, sum_start)

Submission status: Accepted

Solution code:
def nod(a, b):
    if a == 0:
        return b
    elif a > b:
        return nod(a % b, b)
    return nod(b % a, a)


a, b, c, d = map(int, input().split())
ac = a + (c - a % c) % c
ad = a + (d - a % d) % d
bc = b - b % c
bd = b - b % d
dc = c*d//nod(c,d)
acd=a + (dc - a % dc) % dc
bcd = b - b % dc
print(b-a+1-(max(0,(bc-ac)//c+1)+max(0,(bd-ad)//d+1)-max(0,(bcd-acd)//dc+1)))

Submission status: Accepted

Solution code:
import sys
from math import ceil
from operator import itemgetter as get

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

def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def rinput():
    return map(int, tinput())

def rlinput():
    return list(rinput())

def nod(a, b):
    while b: 
        a, b = b, a % b
    return a
 
def calc(n, c, d):
    return n - n // c - n // d + n // (c * d // nod(c, d))   


def main():
    a, b, c, d = rinput()
    print(calc(b, c, d) - calc(a - 1, c, d))
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
all = B-A+1
X = fractions.gcd(C,D)
gC = B//C - ((A-1)//C)
gD = B//D - ((A-1)//D)
gcdcd = C*D//X
gCD = B//gcdcd - ((A-1)//gcdcd)
ans = all - (gC+gD -gCD)
print(ans)

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = [int(i) for i in input().split()]
def lcm(a,b):
    return a*b // fractions.gcd(a,b)
lcm = lcm(C,D)
aa = ((B//C)-(1 if A%C != 0 else 0))-(A//C)+1
bb = ((B//D)-(1 if A%D != 0 else 0))-(A//D)+1
ll = ((B//lcm)-(1 if A%lcm != 0 else 0))-(A//lcm)+1
print(int((B-A+1)-(aa+bb-ll)))

Submission status: Accepted

Solution code:
import math


# 最大公約数gcd,
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


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

cd = lcm(c, d)
r = b - a + 1

min_c = a // c + (1 if a % c != 0 else 0)
max_c = b // c
min_d = a // d + (1 if a % d != 0 else 0)
max_d = b // d
min_cd = a // cd + (1 if a % cd != 0 else 0)
max_cd = b // cd

c_num = max_c - min_c + 1
d_num = max_d - min_d + 1
cd_num = max_cd - min_cd + 1

print(r - c_num - d_num + cd_num)

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

Submission status: Accepted

Solution code:
#まだ自信をもっと答えられないんだよな
#掛け算じゃなくて最小公倍数や
#デバッグの後消す
import fractions
a,b,c,d=[int(i) for i in input().split()]
c1=b//c-a//c
if a%c==0:
    c1+=1
d1=b//d-a//d
if a%d==0:
    d1+=1
cd1=b//(c*d//fractions.gcd(c,d))-a//(c*d//fractions.gcd(c,d))
if a%(c*d)==0:
    cd1+=1
#print(c1)
#print(d1)
#print(cd1)
print(b-a+1-c1-d1+cd1)
#役立つhttps://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e

Submission status: Accepted

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

num = b-a+1
e = b//c - (a-1)//c 
f = b//d - (a-1)//d
g = c*d//gcd(c, d)
print(num - e - f + b//g - (a-1)//g)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
lcm = int((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

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

CD=int(C*D/gcd(C,D))
Ac=A if A%C==0 else A+(C-A%C)
Ad=A if A%D==0 else A+(D-A%D)
Acd=A if A%CD==0 else A+(CD-A%CD)

Rc=(B-Ac)//C+1 if Ac>=A and Ac<=B else 0
Rd=(B-Ad)//D+1 if Ad>=A and Ad<=B else 0
Rcd=(B-Acd)//CD+1 if Acd>=A and Acd<=B else 0

print(B-A+1-(Rc+Rd-Rcd))

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
import fractions
 
def num_divide(p, q, r):
    if p % r == 0:
        rmin = p
    else:
        rmin = p + (r-p%r)
    rmax = q - q%r
    return (rmax-rmin)//r + 1
 
print(b - a + 1 - (num_divide(a, b, c) + num_divide(a, b, d) - num_divide(a, b, c * d // fractions.gcd(c, d))))