Problem:


Score : 300 points

Problem Statement

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

Constraints

1\leq A\leq B\leq 10^{18}

1\leq C,D\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

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

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

Solution code:
import fractions


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


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

a -= 1  # a 以上
x = lcm(c, d)
A = a - (a // c + a // d - a // x)
B = b - (b // c + b // d - b // x)

print(B - A)

Submission status: Accepted

Solution code:
def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
def lcm(a, b):
  return a // gcd(a, b) * b
def f(n, a, b):
  return n - n // a - n // b + n // lcm(a, b)

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

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
#C,Dで割り切れるもの
C=b//c-(a-1)//c
D=b//d-(a-1)//d

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

e=lcm(c,d)
E=b//e-(a-1)//e

print((b-a+1)-(C+D-E))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    ans = "Good"
    for i in range(len(S)-1):
        if S[i+1]==S[i]:
            ans = "Bad"
    print(ans)
    return

def examB():
    N, L = LI()
    ans = 0
    if L>=0:
        for i in range(N - 1):
            ans += (L + i + 1)
    else:
        for i in range(N):
            ans += (L+i)
        if L+N-1<0:
            ans -=(L+N-1)
    print(ans)
    return

def gcd(x, y):
    if y == 0:
        return x
    while y != 0:
        x, y = y, x % y
    return x
def lcm(x, y):
    return x * y // gcd(x, y)
def examC():
    A, B, C, D = LI()
    CD = lcm(C,D)
    ans = B - (B//C + B//D - B//CD) - ((A-1) - ((A-1)//C + (A-1)//D - (A-1)//CD))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
if a == b:
    if a % c != 0 and a % d != 0:
        print(1)
    else:
        print(0)
    exit()
cd_lcm = c * d // gcd(c, d)
print(b - a + 1 - (b // c - (a-1) // c) - (b // d - (a-1) // d) + (b // cd_lcm - (a-1) // cd_lcm))

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())
a=  a-1

c_a = a//c
c_b = b//c

d_a = a//d
d_b = b//d

lcm = lcm(min(c, d), max(c,d))

l_a = a//lcm
l_b = b//lcm




ans =  (b - a)  -  (c_b - c_a) - (d_b - d_a) + (l_b - l_a)

print(ans)

Submission status: Accepted

Solution code:
A,B,C,D = map(int,input().split())
def GCD(x,y):
    if y == 0:
        return x
    return GCD(y,x%y)
A -= 1
GCF = C*D // GCD(C,D)
ans =B-A - (B//C + B//D - (B//GCF) - (A//C + A//D -(A//GCF)))
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

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

    quotient = []
    temp_lcm = c * d // fractions.gcd(c, d)
    for i, x in enumerate([c, d, temp_lcm]):
        temp = (b // x) - ((a-1) // x)
        quotient.append(temp)
    temp1 = b - a + 1
    ans = temp1 - (quotient[0] + quotient[1]) + quotient[2]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions

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

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

b_count=b-(b//c+b//d-b//cd_lcm)
a_count=a-1-((a-1)//c+(a-1)//d-(a-1)//cd_lcm)

print(int(b_count-a_count))

Submission status: Accepted

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

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

lcmCD = lcm(C, D)

divB = (B // C) + (B // D) - (B // lcmCD)
divA_1 = ((A - 1) // C) + ((A - 1) // D) - ((A - 1) // lcmCD)
print((B - A) - (divB - divA_1) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
lcm = lambda a,b: a*b//gcd(a,b)
A, B, C, D = map(int, input().split())
E = (A-1)//C+(A-1)//D-(A-1)//lcm(C,D)
F = B//C+B//D-B//lcm(C,D)
print(B-A+1-(F-E))

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = [int(s) for s in 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:
import math


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


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


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

# 最小公倍数
cd = lcm(c, d)

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

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

lcmCD = lcm(C, D)

divB = (B // C) + (B // D) - (B // lcmCD)
divA_1 = ((A - 1) // C) + ((A - 1) // D) - ((A - 1) // lcmCD)
print((B - A) - (divB - divA_1) + 1)

Submission status: Accepted

Solution code:
# (A ~ B までの個数) - (Cで割り切れるもの + Dで割り切れるもの - CDの最小公倍数で割り切れるもの)
A,B,C,D = list(map(int, input().split()))

def euc(a, b):
    a, b = [max(a, b), min(a, b)]
    if b == 0:
        return a
    else:
        return euc(b, a % b)

Cdiv = (B // C) - ((A-1) // C)
Ddiv = (B // D) - ((A-1) // D)
E = (C * D) // euc(C, D)
CDdiv = (B // E) - ((A-1) // E)

print((B - A + 1) - (Cdiv + Ddiv - CDdiv))

Submission status: Accepted

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

	#about c
	ans_c_a = (a-1)//c
	ans_c_b = b//c
	# print(ans_c_b)
	ans_c = ans_c_b - ans_c_a
	# print("ans_c = {}".format(ans_c))

	#about d
	ans_d_a = (a-1)//d
	ans_d_b = b//d
	ans_d = ans_d_b - ans_d_a
	# print("ans_d = {}".format(ans_d))

	#aboud c*d
	import fractions
	saisyou = (c * d) // fractions.gcd(c,d)
	# print(saisyou)
	ans_saisyou_a = (a-1)//saisyou
	ans_saisyou_b = b//saisyou
	ans_saisyou = ans_saisyou_b - ans_saisyou_a
	# print("ans_saisyou = {}".format(ans_saisyou))

	print(int( b-a+1 - (ans_c + ans_d - ans_saisyou) ))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# 21:15
import fractions as math

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

def F(n,c,d):
    x = n
    x -= n//c
    x -= n//d
    lcm = c*d//math.gcd(c,d)
    x += n//lcm
    return x

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

Submission status: Accepted

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


def calc_anti(N, C, D):
    lcm = C * D // gcd(C, D)
    div = N // C + N // D - N // lcm
    return N - div


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

Submission status: Accepted

Solution code:
import fractions
A,B,C,D=map(int, input().split())
def ans_mthd(i, j, k):
    return (i - i // j - i // k + i * fractions.gcd(j, k) // j // k )
ans = ans_mthd(B, C, D)-ans_mthd(A-1, C, D)
print(ans)

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

Submission status: Accepted

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

def gcm(x, y):
    x, y = max(x, y), min(x, y)
    if y == 0:
        return x
    else:
        return gcm(y, x%y)

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

def canDevide(n, x, y):
    return n - n//x - n//y + n//lcm(x, y)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y
x=gcd(c,d)
ans1=b-b//c-b//d+b//(c*d//x)
a-=1
ans2=a-a//c-a//d+a//(c*d//x)
print(ans1-ans2)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
a,b,c,d = map(int,input().split())
l =[c, d]
num = a // c
if a%c==0:
  num -= 1
num1 = b // c
num2 = a // d
if a%d==0:
  num2 -= 1
num3 = b// d
e = lcmm(l)
num4 = a // e
if a%e==0:
  num4 -= 1
num5 = b // e
print((b-a+1)-((num1-num)+(num3-num2)-(num5-num4)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
cnum = B//C-(A-1)//C
dnum = B//D-(A-1)//D
mx = max(C, D)
mn = min(C, D) 
while mn != 0:
    mx, mn = mn, mx%mn
    #print(mx)
    E = int(C*D/mx)
enum = B//E-(A-1)//E
ansback = cnum+dnum-enum
ans = B-A+1-ansback
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
A,B,C,D = map(int,input().split())
def lcm(a,b):
    return (a*b)//fractions.gcd(a,b)
def solve(n,a,b):
    return n - (n//a + n//b - n//lcm(a,b))
print(solve(B,C,D)-solve(A-1,C,D))

Submission status: Accepted

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

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 f(n):
    res = n
    res -= n // C
    res -= n // D
    res += n // lcm(C, D)

    return res

ans = f(B) - f(A - 1)

print(ans)

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

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

def not_devide(i):
  ans = i - i//C - i//D + i//cd_lcm
  
  return ans

print(not_devide(B) - not_devide(A-1))

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D = list(map(int, input().split()))
def lcm(x, y):
    return (x * y) // gcd(x, y)
lcm = lcm(C,D)
nbc = B//C
nbd = B//D
nbl = B//lcm 
nac = (A-1)//C
nad = (A-1)//D
nal = (A-1)//lcm 
ans = B - A + 1-((nbc+nbd-nbl)-(nac+nad-nal))
print(int(ans))

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


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

from1toA = (a - 1) - ((a - 1) // c + (a - 1) // d - (a - 1) // lcm)
from1toB = b - (b // c + b // d - b // lcm)
fromAtoB = from1toB - from1toA

print(fromAtoB)

Submission status: Accepted

Solution code:
import sys
import fractions
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

A, B, C, D = MAP()
# Cで割り切れる数 = B/C - A/C
c_b = B//C
c_a = A//C if A%C else A//C-1
c = c_b-c_a

d_b = B//D
d_a = A//D if A%D else A//D-1
d = d_b-d_a

E = (C*D) // (fractions.gcd(C,D))
#print(E)
e_b = B//E
e_a = A//E if A%E else A//E-1
e = e_b - e_a

#print(c, d, e)

print((B-A+1)-(c+d-e))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
a=a-1
ac,ad,bc,bd=a//c,a//d,b//c,b//d

f=fractions.gcd(c,d)
f=c*d//f
acd,bcd=a//f,b//f
print((b-a)-(bc-ac)-(bd-ad)+(bcd-acd))

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())
c = 0

Ac = (A-1)//C
Ad = (A-1)//D
Bc = B//C
Bd = B//D
cd = ((C*D)//gcd(C,D))
Acd = (A-1)//cd
Bcd = B//cd
print((B-Bc-Bd+Bcd) - (A-Ac-Ad+Acd)+1)

Submission status: Accepted

Solution code:
import sys
def gcd(x, y):
    while True:
        if x > y:
            x %= y
        else:
            y %= x
        if x == 0 or y == 0:
            break
    return max(x, y)

a, b, c, d = [int(i) for i in sys.stdin.readline().split()]
gcd_cd = gcd(c, d)
lcm = c * d // gcd_cd
n_c = b // c - (a - 1) // c
n_d = b // d - (a - 1) // d
n_cd = b // lcm - (a - 1) // lcm
res = (b - a + 1) - n_c - n_d + n_cd
print(res)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
#from scipy.misc import comb

MOD = 10**9+7

def gcd(A,B):
    if B>A:
        A,B = B,A

    if(A%B==0):
        return B
    else:
        return gcd(B,A%B)

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

L = (A-1)-((A-1)//C+(A-1)//D-(A-1)//(C*D//gcd(C,D)))
U = B-(B//C+B//D-B//(C*D//gcd(C,D)))

print(U-L)

Submission status: Accepted

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

def f(x):
  l=x//C
  m=x//D
  k=C*D//gcd(C,D)
  n=x//k
  
  return(x-l-m+n)

print(f(B)-f(A-1))

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
g = fractions.gcd(C,D)
l = C*D//g
print(B-A+1-B//C-B//D+B//l+(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 = c*d // fractions.gcd(c,d)


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

ans = b_num - a_num
print(ans)

Submission status: Accepted

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


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


def g(n, c, d):
    return n - n // c - n // d + n // lcm(c, d)


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

Submission status: Accepted

Solution code:
import fractions

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

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


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

ans = b_num - a_num
print(ans)

Submission status: Accepted

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


def main():
    sc = Scan()
    A, B, C, D = sc.intarr()
    div_b = B//C + B//D - B//(lcm(C, D))
    div_a = (A-1)//C + (A-1)//D - (A-1)//(lcm(C, D))

    ans = B - (A-1) - div_b + div_a

    print(ans)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


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


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


main()

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

Submission status: Accepted

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

a, b, c , d = [int(x) for x in input().split()]

x = a//c
if a%c != 0:
  x += 1
y = a//d
if a%d != 0:
  y += 1
dd = (c*d)//gcd(c, d)
xy = a//(dd)
if a%(dd) != 0:
  xy += 1

t1 = max(0, b//c - x+1)
t2 = max(0, b//d - y+1)
t3 = max(0, b//(dd) - xy+1)

print(str((b-a+1) - (t1+t2-t3)))

Submission status: Accepted

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

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

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


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

print((b-a+1)-(x-y))

Submission status: Accepted

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


def start(num: int) -> int:
    if A % num == 0:
        num_start = A + (A % num)
    else:
        num_start = A + (num - A % num)
    return num_start


def count_in_range(num_start: int, num: int) -> int:
    r = B - num_start
    return r // num + 1


def calc(num: int) -> int:
    return count_in_range(start(num), num)


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


c = calc
print((B - A + 1) - (calc(C) + calc(D) - calc(lcm(C, D))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A = 0
B = 0
C = 0
D = 0


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


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


def f(n):
    return n - n // C - n // D + n // lcm(C, D)


def main():
    global A, B, C, D
    A, B, C, D = map(int, input().split())
    print(f(B) - f(A - 1))
    return


main()

Submission status: Accepted

Solution code:
import math
import fractions

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

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

ans = 0
lcm = lcm_base(C,D)
c_num = B//C - (A-1)//C 
d_num = B//D - (A-1)//D
diff = B//lcm - (A-1)//lcm

print(B-A+1-(c_num+d_num-diff))

Submission status: Accepted

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

#A-Bの中でCで割れる最小数
if A%C==0:
  lowC=A//C
else:
  lowC=A//C+1
#A-Bの中でCで割れる最大数
highC=B//C
numC = (highC-lowC)+1

#A-Bの中でDで割れる最小数
if A%D==0:
  lowD=A//D
else:
  lowD=A//D+1
#A-Bの中でDで割れる最大数
highD=B//D
numD = (highD-lowD)+1


#まず最大公約数を求める
a=C
b=D
if a<b:a,b=b,a
while a%b!=0:
  a,b=b,a%b
gcd=b
#CとDの最小公倍数
lcm=C*D//gcd

#A-Bの中でlcmで割れる最小数
if A%lcm==0:
  lowlcm=A//lcm
else:
  lowlcm=A//lcm+1
#A-Bの中でlcmで割れる最大数
highlcm=B//lcm
numlcm = (highlcm-lowlcm)+1
total=((numC+numD)-numlcm)
print(((B-A)+1)-total)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def lcm(x, y):
    return x * y // gcd(x, y)
def gcd(x, y):
    if y== 0:
        return x
    else:
        return gcd(y, x % y)
A -= 1
# A-1以下でC, Dで割り切れる数
a = (A // C + A // D) - A // lcm(C, D)
# B以下でC, Dで割り切れる数
b = (B // C + B // D) - B // lcm(C, D)

print(B-A-(b-a))

Submission status: Accepted

Solution code:
import fractions as f

A, B, C, D = list(map(int, input().split()))
A = A - 1
lcmCD = C * D // f.gcd(C, D)
underB = B - B // C - B // D + B // lcmCD
underA = A - A // C - A // D + A // lcmCD
print(underB - underA)

Submission status: Accepted

Solution code:
#131 C
import sys
import fractions
a,b,c,d = map(int, sys.stdin.readline().split())
#print(a,b,c,d)

dc = b//c - (a-1)//c
dd = b//d - (a-1)//d
lcm = (c*d)//fractions.gcd(c, d)

dcd = b//lcm -(a-1)//lcm
#print(dc, dd, dcd)

ans = b-(a-1) -(dc+dd) + dcd
print(int(ans))

Submission status: Accepted

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

import fractions

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

E = lcm(C, D)

n_a = (A - 1) // C + (A - 1) // D - (A - 1) // E
n_b = B // C + B // D - B // E

print((B - A + 1) - (n_b - n_a))

Submission status: Accepted

Solution code:
import fractions as ff
a,b,c,d=map(int,input().split())
if a%c==0 or a%d==0:
    cnt=1
else:
    cnt=0
if cnt==1:
    print((b-b//c-b//d+b//(c*d//ff.gcd(c,d)))-(a-a//c-a//d+a//(c*d//ff.gcd(c,d))))
else:
    print((b-b//c-b//d+b//(c*d//ff.gcd(c,d)))-(a-a//c-a//d+a//(c*d//ff.gcd(c,d)))+1)

Submission status: Accepted

Solution code:
import fractions

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

def func(n, x, y):
    lcm = x * y // fractions.gcd(x, y)
    return n - (n // x + n // y - n // lcm)

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

BperC = B // C
AperC = (A - 1) // C
BperD = B // D
AperD = (A - 1) // D
BperCD = B // (C * D // gcd(C, D))
AperCD = (A - 1) // (C * D // gcd(C, D))

AB = B - (A - 1)
ABperC = BperC - AperC
ABperD = BperD - AperD
ABperCD = BperCD - AperCD

out = AB - ((ABperC + ABperD) - ABperCD)
print(out)

Submission status: Accepted

Solution code:
def gcd(c,d):
  if d==0:
    return c
  else:
    t=c%d
    return gcd(d,t)

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

Submission status: Accepted

Solution code:
import fractions

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

e = c * d // fractions.gcd(c,d)
c_count = b // c - a // c
if a % c == 0:
    c_count += 1
d_count = b // d - a // d
if a % d == 0:
    d_count += 1
e_count = b // e - a // e
if a % e == 0:
    e_count += 1

ans = b - a + 1 - (c_count + d_count - e_count)

print(ans)

Submission status: Accepted

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

a,b,c,d = map(int, input().split())
cd = lcm(c,d)
a -= 1
a_cnt = a - (a//c + a//d - a//cd)
b_cnt = b - (b//c + b//d - b//cd)
print(b_cnt - a_cnt)

Submission status: Accepted

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

ac=a//c
ad=a//d
bc=b//c
bd=b//d

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

acd=a//f
bcd=b//f

print((b-a)-(bc-ac)-(bd-ad)+(bcd-acd))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
if d>c:
  euclid2,euclid1=c,d
  e1,e2=euclid1,euclid2
  while not euclid2==0:
    euclid1=euclid1%euclid2
    euclid1,euclid2=euclid2,euclid1
    cd=c*d//euclid1
else:
  euclid2,euclid1=d,c
  e1,e2=euclid1,euclid2
  while not euclid2==0:
    euclid1=euclid1%euclid2
    euclid1,euclid2=euclid2,euclid1
    cd=c*d//euclid1
  
c1=(a-1)//c+1
c2=(b-c1*c)//c+1
d1=(a-1)//d+1
d2=(b-d1*d)//d+1
cd1=(a-1)//cd+1
cd2=(b-cd1*cd)//cd+1  
print(b-a+1-c2-d2+cd2)

Submission status: Accepted

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

Submission status: Accepted

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

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


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

af=(a-1)//f
bf=b//f



print((b-a+1)-(bc-ac)-(bd-ad)+(bf-af))

Submission status: Accepted

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

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

def num_div(first, last, div):
  return last//div - (first-1)//div

c_div = num_div(a, b, c)
d_div = num_div(a, b, d)
cd_div = num_div(a, b, lcm(c, d))

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

Submission status: Accepted

Solution code:
a,b,c,d= map(int,input().split())
k=b+1-a
n=(b//d)-((a-1)//d)
m=(b//c)-((a-1)//c)
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
     return a*b//gcd(a,b)
l=(b//(lcm(c,d)))-((a-1)//(lcm(c,d)))
print(k+l-n-m)

Submission status: Accepted

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

lcm = C*D // fractions.gcd(C, D)
A-=1
a = A//C + A//D - A//lcm
b = B//C + B//D - B//lcm

print(B-A-b+a)

Submission status: Accepted

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

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

# a <= n, n <= bの整数のうち c, dで割り切れる数
c_div = (b // c) - ((a-1) // c)
d_div = (b // d) - ((a-1) // d)


# a <= n, n <= bの整数のうち c,dの最小公倍数で割り切れる数
c_d = lcm(c, d)
c_d_div = (b // c_d) - ((a-1) // c_d)

# a <= n, n <= bの整数の数
i_count = b - a + 1

print(i_count - (c_div + d_div - c_d_div))

Submission status: Accepted

Solution code:
import math
import fractions
(a,b,c,d)=map(int,input().split())
g=c*d//fractions.gcd(c,d)
k=0
k+=b//c+b//d-b//g-int(a-1)//c-(a-1)//d+(a-1)//g

print(b-a+1-k)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

input = sys.stdin.readline

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

def main():
    A, B, C, D = map(int, input().split())
    
    c = B // C - A // C + (not A % C)
    d = B // D - A // D + (not A % D)
    
    x = lcm(C, D)
    x = B // x - A // x + (not A % x)
    
    print(B-A+1-c-d+x)
    
if __name__ == '__main__':
    main()

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())
t = b - a + 1

e = (b//c - a//c)
if a % c == 0:
  e += 1
f = (b//d - a//d)
if a % d == 0:
  f += 1

h = lcm(c, d)  
g = b//h - a//h
if a % h == 0:
  g += 1
print(t - (e+f-g))

Submission status: Accepted

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

print(n2-n1)

Submission status: Accepted

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

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

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

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

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)

c_num = (B//C - (A-1)//C)
d_num = (B//D - (A-1)//D)
cd_num = (B//lcm(C, D) - (A-1)//lcm(C, D))
print((B-A+1) - (c_num+d_num-cd_num))

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

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)
def func(n,x,y):
  return n - (n//x + n//y - n//lcm(x,y))
ans = func(b,c,d) - func(a-1,c,d)
print(ans)

Submission status: Accepted

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

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

a, b, c, d = map(int, input().split())
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
#解説見ました。
def lcm(x,y):
    return (x * y) // fractions.gcd(x,y)
def wei(n,x,y):
    return n-(n//x + n//y - n//lcm(x,y))

A,B,C,D = [int(i) for i in input().split(" ")]
print(wei(B,C,D) - wei(A-1,C,D))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

def cnt_mod0(st, ed, x):
    c = 0
    if st % x !=0: st = x * (st // x + 1)
    if st > ed:return 0
    c = (ed-st) // x + 1
    return c

cnt = B- A + 1 - (cnt_mod0(A, B, C) + cnt_mod0(A, B, D) - cnt_mod0(A, B, cd_lcm))
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x
def calc(x, C, D, l):
    x1 = x // C
    x2 = x // D
    x3 = x // l
    return x - x1 -x2 + x3

def print_ans(A, B, C, D):
    """Test Case
    >>> print_ans(4, 9, 2, 3)
    2
    >>> print_ans(10, 40, 6, 8)
    23
    >>> print_ans(314159265358979323, 846264338327950288, 419716939, 937510582)
    532105071133627368
    """
    # Greatest common divisor
    g = gcd(max(C,D),min(C,D))
    # Least common multiple
    l = C * D // g
    print(calc(B, C, D, l) - calc(A - 1, C, D, l))



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

Submission status: Accepted

Solution code:
import math
import fractions
A,B,C,D = map(int,input().split())
def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)
def cal(n,x,y):
    return n-(n//x + n//y - n//lcm(x,y))
print(cal(B,C,D)-cal(A-1,C,D))

Submission status: Accepted

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

Submission status: Accepted

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

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

def calc(n: int, a: int, b: int) -> int:
    return n - (n//a + n//b - n//(lcm(a, b)))

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

def F(N):
  x = N//C
  x += N//D
  lcm = C*D//gcd(C,D)
  x -= N//lcm
  return N-x

print(F(B)-F(A-1))