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

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

m = int(c*d/gcd(c,d))
xc = b//c - (a-1)//c
xd = b//d - (a-1)//d
xm = b//m - (a-1)//m
print(b-a+1-xc-xd+xm)

Submission status: Accepted

Solution code:
# 逆に公倍数を引く。B-A+1-(Cの倍数の数+Dの倍数の数-CとDの公倍数の数)
a, b, c, d = map(int, input().split())


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


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


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

Submission status: Accepted

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

# 最大公約数。Euclidの互除法.
def gcd(m, n):
  if m < n:
    return gcd(n, m)
  if m%n == 0:
    return n
  else:
    return gcd(n, m%n)

# 最小公倍数
l = c*d//gcd(c,d)
def lowX(x,c,d,l):
  ans = x - x//c - x//d + x//l
  return ans
lowB = lowX(b,c,d,l)
lowA = lowX(a-1,c,d,l)
print(int(lowB-lowA))

Submission status: Accepted

Solution code:
from sys import stdin




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



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

c_num = b//c-(a-1)//c
d_num = b//d-(a-1)//d

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

ans = b-a+1
ans -= c_num
ans -= d_num
ans += b//LCM-(a-1)//LCM
print(ans)

Submission status: Accepted

Solution code:
import fractions
 
a,b,c,d = map(int,input().split())
 
ans = 0
 
if c % d == 0:
    print((b - a + 1) - ((b)//d - (a-1)//d))
elif d % c == 0:
    print((b - a + 1) - ((b)//c - (a-1)//c))
else:
    tot = c * d // fractions.gcd(c, d)
    tmp = ((b) // d - (a-1) // d) + ((b)//c - (a-1)//c) - ((b) // tot - (a-1) // tot)
    print(int((b - a + 1) - tmp))

Submission status: Accepted

Solution code:
def GCD(a,b):
  if a<b:
    tmp = a
    a = b
    b = tmp
 
  r = a % b
  while (r!=0): 
    a = b
    b = r
    r = a % b
  return b


A,B,C,D = map(int,input().split())
A = A - 1
upperC = int(B // C)
upperD = int(B // D)
lowerC = int(A // C)
lowerD = int(A // D)

numC = upperC - lowerC
numD = upperD - lowerD

gcd = GCD(C,D)

lcm = C * D // gcd
upperL = int(B // lcm)
lowerL = int(A // lcm)
numL = upperL - lowerL

print(str(B - A - (numC + numD - numL)))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

def lcm(c,d):
    return c*d//fractions.gcd(c,d)

def dev_count(n,c,d):
    x = n
    n -= x//c
    n -= x//d
    n += x//(lcm(c,d))
    return n

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

Submission status: Accepted

Solution code:
from fractions import gcd


def f(a, m, n):
    l = m * n // gcd(m, n)
    return a - (a // m) - (a // n) + a // l


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


if __name__ == "__main__":
    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())

LCM = lcm(C, D)

x = B//C
y = B // D
z = B // LCM
ans = B-x-y+z

x = (A-1) // C
y = (A-1) // D
z = (A-1) // LCM

ans -= (A-1) - x - y + z

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b,c,d = LI()
    g = fractions.gcd(c,d)
    t = c * d // g
    e = b // c - (a-1) // c
    f = b // d - (a-1) // d
    h = b // t - (a-1) // t

    return (b-a+1) - e - f + h


print(main())

Submission status: Accepted

Solution code:
from fractions import gcd

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

N = B - (A-1)
M_C = (B // C) - ((A-1) // C)
M_D = (B // D) - ((A-1) // D)
M_CD = (B // lcm) - ((A-1) // lcm)
M = M_C + M_D - M_CD

print(N-M)

Submission status: Accepted

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

p = (b-b//c-b//d+b//(c*d//gcd(c,d)))
q = (a-a//c-a//d+a//(c*d//gcd(c,d)))
print(p-q)

Submission status: Accepted

Solution code:
from fractions import gcd

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

nums = b - a + 1
c_count = b // c - a // c + 1 if a % c == 0 else b // c - a // c
d_count = b // d - a // d + 1 if a % d == 0 else b // d - a // d
lcm = c * d // gcd(c, d)
lcm_count = b // lcm - a // lcm + 1 if a % lcm == 0 else b // lcm - a // lcm
print(nums - c_count - d_count + lcm_count)

Submission status: Accepted

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

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

def num(N,c,d):
    lcm = (c*d)//gcd(c,d)
    return N - (N//c) - (N//d) +  N//lcm

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

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)

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

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

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)

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

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

Submission status: Accepted

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

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

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

a1 = -(-A // C)
a2 = -(-A // D)
a3 = -(-A // lcm(C,D))

b1 = B // C
b2 = B // D
b3 = B // (lcm(C,D))

ans = (B-A+1) - ((b1-a1+1) + (b2-a2+1) - (b3-a3+1))
print(ans)

Submission status: Accepted

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

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a%b)
 
def lcm(a, b):
  return a*b // gcd(a,b)
 
x = lcm(C, D)
 
print((B-A+1) - (B//C) + ((A-1)//C) - (B//D) + ((A-1)//D) + (B//x) - ((A-1)//x))

Submission status: Accepted

Solution code:
from math import floor
from fractions import gcd


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


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

LCM = lcm(C, D)

x = B // C
y = B // D
z = B // LCM
ans = B-x-y+z

x = (A-1) // C
y = (A-1) // D
z = (A-1) // LCM

ans -= (A-1) - x - y + z

print(ans)

Submission status: Accepted

Solution code:
A,B,C,D = map(int,input().split())
def f(B,n):
  return B//n
def gcd(a,b):
  if b==0:return a
  return gcd(b,a%b)
E = C*D//gcd(C,D)
print(B - f(B,C) - f(B,D) + f(B,E) - (A-1 - f(A-1,C) - f(A-1,D) + f(A-1,E)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def lcm(a,b):
    A,B=a,b
    while b!=0:
        a,b=b,a%b
    return A*B//a
 
def count(a,b,c):
    return b//c-(a-1)//c
 
A,B,C,D=map(int,input().split())
C_count = count(A,B,C)
D_count = count(A,B,D)
CD_count = count(A,B,lcm(C,D))
ans = B - (A - 1) - (C_count + D_count - CD_count)
print("{}".format(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def lcm(a,b):
    A,B=a,b
    while b!=0:
        a,b=b,a%b
    return A*B//a

def count(a,b,c):
    return b//c-(a-1)//c

A,B,C,D=map(int,input().split())
C_count = count(A,B,C)
D_count = count(A,B,D)
CD_count = count(A,B,lcm(C,D))
ans = B - (A - 1) - (C_count + D_count - CD_count)
print("{}".format(ans))

Submission status: Accepted

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

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

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

E = lcm(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:
import fractions

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

Submission status: Accepted

Solution code:
from fractions import gcd

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


# CまたはDで割り切れる数を求め、それを差し引いて求める
def f(x):
    return x - (x // C + x // D - x // (C * D // gcd(C, D)))


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

# 出力
print(ans)

Submission status: Accepted

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

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

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

A = A -1
c_num = B//C - A//C
d_num = B//D - A//D
    
lcm_num = lcm(C, D)

cd_num = B//lcm_num - A//lcm_num
    
print(B - A - c_num - d_num + cd_num)

Submission status: Accepted

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

tmp = max(C, D)


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


E = lcm(C, D)

aC = (A - 1) // C
aD = (A - 1) // D
aE = (A - 1) // E
bC = B // C
bD = B // D
bE = B // E

aS = aC + aD - aE
bS = bC + bD - bE
sum = B - (A - 1) - (bS - aS)

print(sum)

Submission status: Accepted

Solution code:
A, B, C, D = list(map(int, input().split()))
from fractions import gcd
e = C * D // gcd(C, D)
p1 = B-A+1
p2 = (B//C) + (B//D) - (B//e)
p3 = ((A-1)//C) + ((A-1)//D) - ((A-1)//e)
print(p1 + p3 - p2)

Submission status: Accepted

Solution code:
#最大公約数(ユークリッドの互余法)
def euclid_gcd(a,b):
    while b:
        a, b = b, a % b
    return a

#最小公倍数(ユークリッドの互余法)
def euclid_lcm(a, b):
    return a * b // euclid_gcd(a, b)
    
A,B,C,D = map(int,input().split())

X = euclid_lcm(C,D)
A = A-1

Y = A//C + A//D - A//X
Z = B//C + B//D - B//X
 
print(B-Z - (A-Y))

Submission status: Accepted

Solution code:
def lcm(a, b):
    x = a * b
    if a < b:
        a, b = b, a
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b

    return x // b


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

_lcm = lcm(D, C)

nA = (A - 1) // C + (A - 1) // D - (A - 1) // _lcm
nB = B // C + B // D - B // _lcm
print((B - A + 1) - (nB - nA))

Submission status: Accepted

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


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


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


num1 = B // C - (A - 1) // C
num2 = B // D - (A - 1) // D
num3 = B // lcm(C, D) - (A - 1) // lcm(C, D)


print(B - A + 1 - (num1 + num2 - num3))

Submission status: Accepted

Solution code:
import fractions

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

if B//lcm==0:
    num_CD=0
else:
    num_CD=B//lcm-(A-1)//lcm


if B//C==0:
    num_C=0
else:
    num_C=B//C-(A-1)//C



if B//D==0:
    num_D=0
else:
    num_D=B//D-(A-1)//D


ans=B-A+1-num_C-num_D+num_CD


print(int(ans))

Submission status: Accepted

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

import sys
import copy

sys.setrecursionlimit(1000000)


# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~

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


def LCM(x, y):
    return x // GCD(x, y) * y


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

S = B - A + 1

canC = B // C - (A - 1) // C
canD = B // D - (A - 1) // D
canCD = B // LCM(C, D) - (A - 1) // LCM(C, D)

print(S - (canC + canD) + canCD)

Submission status: Accepted

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

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)

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

print(ans)

Submission status: Accepted

Solution code:
#import math
import fractions as math

A, B, C, D = list(map(int, input().split()))
ans = []
x = int((C*D)/math.gcd(C,D))

for n in [A-1, B]:
    c = n // C
    d = n // D
    cd = n // x
    ans.append(n-c-d+cd)
print(ans[1]-ans[0])

Submission status: Accepted

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

def gcd(c, d):
    while d:
        c, d = d, c % d
    return c

lcm = c * d // 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)
print(int(b_num - a_num))

Submission status: Accepted

Solution code:
import math

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

def gcd(C,D):
    if D==0:
        return C
    else:
        return gcd(D,C%D)

U=B-A+1
num1=B//C-(A-1)//C + B//D-(A-1)//D
x=C//gcd(C,D)*D
num2=B//x-(A-1)//x
print(U-num1+num2)

Submission status: Accepted

Solution code:
from fractions import gcd


def NonDivNum(n):
    if n == 0:
        return 0
    else:
        return n - n//C - n//D + n//CD


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

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


a, b, c, d = MI()
under_b_cdiv = b // c
under_b_ddiv = b // d
under_b_cddiv = b // LCM(c, d)
B = b - (under_b_cdiv + under_b_ddiv - under_b_cddiv)
under_a1_cdiv = (a - 1) // c
under_a1_ddiv = (a - 1) // d
under_a1_cddiv = (a - 1) // LCM(c, d)
A = (a - 1) - (under_a1_cdiv + under_a1_ddiv - under_a1_cddiv)
print(B - A)

Submission status: Accepted

Solution code:
def calc(n,a):
    return n//a

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

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

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

ca = calc(a-1,c)
cb = calc(a-1,d)
cc = calc(a-1,lcm(c,d))
an1 = ca+cb-cc

ca = calc(b,c)
cb = calc(b,d)
cc = calc(b,lcm(c,d))
an2 = ca+cb-cc

print(b-a+1-(an2-an1))

Submission status: Accepted

Solution code:
from fractions import gcd


# 最小公倍数はGCDを使って算出できる
def lcm(a, b):
    return int(a * b / gcd(a, b))


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

# B以下の整数のうち、CでもDでも割り切れないものの個数
cnt_B = B - (B // C + B // D) + B // lcm(C, D)

# A - 1以下の整数のうち、CでもDでも割り切れないものの個数
A_1 = A - 1
cnt_A = A_1 - (A_1 // C + A_1 // D) + A_1 // lcm(C, D)

print(cnt_B - cnt_A)

Submission status: Accepted

Solution code:
import fractions

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

if __name__=="__main__":
    A,B,C,D=map(int,input().split())
    lcm=LCM(C,D)
    count=B//C+B//D-B//lcm
    count1=(A-1)//C+(A-1)//D-(A-1)//lcm
    result=B-A+1-count+count1
    print(int(result))

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split())
if C>D:
  c=D
  d=C
else:
  c=C
  d=D
  
f=B//d
g=(A-1)//d
h=B//c
i=(A-1)//c
  
while c:
  c,d=d%c,c
j=C*D//d
k=B//j
l=(A-1)//j
print(B-A+1-(f-g+h-i-k+l))

Submission status: Accepted

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

Submission status: Accepted

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

def lcm(c,d):
	return (c*d)// fractions.gcd(c,d)

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd


scan = sys.stdin.readline


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


def main():
  a, b, c, d = map(int, scan().rstrip().split())
  
  # swap
  if c > d:
    _ = c
    c = d
    d = _
  
  cd_mul_to_a = -((a-1) // lcm(c, d))
  cd_mul_to_b = -(b // lcm(c, d))
  
  cd_mul_to_a += (a-1) // c
  cd_mul_to_b += b // c
  
  cd_mul_to_a += (a-1) // d
  cd_mul_to_b += b // d
  
  total = (b - a + 1) - (cd_mul_to_b - cd_mul_to_a)
  
  print(total)


main()

Submission status: Accepted

Solution code:
# ABC131 Anti-devision

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

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

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

ab_c = B // C - (A - 1) // C
ab_d = B // D - (A - 1) // D
cd_lcm = lcm(C, D)
ab_cd_lcm = B // cd_lcm - (A - 1) // cd_lcm

ans = B - (A - 1) - ab_c - ab_d + ab_cd_lcm

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

def multiple(A, B, C): #number of multiples of C between A and B
    return B//C - (A-1)//C

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

allnumbers = B-A+1

ans = allnumbers - (multiple(A,B,C) + multiple(A,B,D) - multiple(A,B,lcm(C,D)))

print(ans)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
bc = B // C
bd = B // D
ac = (A - 1) // C
ad = (A - 1) // D
def gcd(C, D):
    while D:
        C, D = D, C % D
    return C
def lcm(C, D):
    return C * D // gcd(C, D)
bcd = B // lcm(C, D)
acd = (A - 1) // lcm(C, D)
a = bc - ac
b = bd - ad
c = bcd - acd
print((B + 1 - A) - (a + b - c))

Submission status: Accepted

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


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

size=B

cd=lcm(C,D)
allC=size//C
allD=size//D
allcd=size//cd
ALL=size-(allC+allD-allcd)

size=A-1
cd=lcm(C,D)
pC=size//C
pD=size//D
pcd=size//cd
P=size-(pC+pD-pcd)

print(ALL-P)

Submission status: Accepted

Solution code:
from fractions import gcd

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


def num(n1,n2,n3):
  return n1 - (n1//n2) - (n1//n3) + (n1//lcm(n2,n3))


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

temp = input().split(" ")
min = int(temp[0])
max = int(temp[1])
divisor1 = int(temp[2])
divisor2 = int(temp[3])
divisors = [divisor1,divisor2] if divisor1 > divisor2 else [divisor2, divisor1]

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

gcdDivisors = gcd(divisors[0], divisors[1]);
lcmDivisors = (divisor1 * divisor2) // gcdDivisors

divNum1 = max // divisor1 - (min - 1) // divisor1;
divNum2 = max // divisor2 - (min - 1) // divisor2;
divNumLcm = max // lcmDivisors - (min - 1) // lcmDivisors;

divNumTotal = divNum1 + divNum2 - divNumLcm;
ans = max - min + 1 - divNumTotal

print(int(ans))

Submission status: Accepted

Solution code:
import fractions as f
a,b,c,d = map(int,input().split())
i = abs((a-1)//c-b//c)
j = abs((a-1)//d-b//d)
 
def lcm(x,y):
  return (x*y)//f.gcd(x,y)
l = lcm(c,d)
k = abs((a-1)//l-b//l)
print(b-a+1-(i+j-k))

Submission status: Accepted

Solution code:
import fractions as f
a,b,c,d = map(int,input().split())
i = abs((a-1)//c-b//c)
j = abs((a-1)//d-b//d)

def lcm(x,y):
  return (x*y)//f.gcd(x,y)
l = lcm(c,d)
k = abs((a-1)//l-b//l)
print(b-a+1-(i+j-k))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x, y):
  return (x * y) // gcd(x, y)
def num(n1,n2,n3):
  return n1-(n1//n2)-(n1//n3)+(n1//lcm(n2,n3))
A,B,C,D=map(int,input().split())
print(num(B,C,D)-num(A-1,C,D))

Submission status: Accepted

Solution code:
from fractions import gcd
Input = input()
a, b, c, d = Input.split()
a, b, c, d = int(a), int(b), int(c), int(d)
delta_c = b//c - (a-1)//c
delta_d = b//d - (a-1)//d
def lcm(x, y):
    return (x * y) // gcd(x, y)
cd = lcm(c, d)
delta_cd = b//cd - (a-1)//cd
num_cd = delta_c + delta_d - delta_cd
print( b-a+1 - num_cd, end='')

Submission status: Accepted

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

Submission status: Accepted

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


lcm = (c * d) // frac.gcd(c,d)
if a % lcm != 0:
    s = lcm - a % lcm
else:
    s = 0
e = b % lcm
m = ((b - e) - (a + s)) // lcm
modgcd = (b - a + 1) - (s + (lcm - 1) * m + e)

if a % c != 0:
    s = c - a % c
else:
    s = 0
e = b % c
m = ((b - e) - (a + s)) // c
modc = (b - a + 1)- (s + (c - 1) * m + e)

if a % d != 0:
    s = d - a % d
else:
    s = 0
e = b % d
m = ((b - e) - (a + s)) // d
modd = (b - a + 1) - (s + (d - 1) * m + e)

print((b - a + 1)-(modc + modd - modgcd))

Submission status: Accepted

Solution code:
import math,fractions
a=list(map(int,input().split()))
A=a[1]-a[0]+1 #もともとのAとBの間の数
B=(a[1]//a[2])-((a[0]-1)//a[2]) #Bの中のCの倍数-Aの中のCの倍数
C=(a[1]//a[3])-((a[0]-1)//a[3]) #Bの中のDの倍数-Aの中のDの倍数
d=a[2]*a[3]//fractions.gcd(a[2],a[3]) #CとDの最小公倍数
D=(a[1]//d)-((a[0]-1)//d) #Bの中の最小公倍数の倍数-Aの中の最小公倍数の倍数
print(A-B-C+D)

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split())
if A%C==0:
    cmin=A//C
else:
    cmin=A//C+1
cmax=B//C
if A%D==0:
    dmin=A//D
else:
    dmin=A//D+1
dmax=B//D
#最大公約数
def gcd(C,D):
  while D!=0:
    C,D=D,C%D
  return C
#最小公倍数
def lcm(C,D):
  return C*D//gcd(C,D)
e=lcm(C,D)
if A%e==0:
    emin=A//e
else:
    emin=A//e+1
emax=B//e
total=(cmax-cmin+1)+(dmax-dmin+1)-(emax-emin+1)
f=B-A+1-total
print(f)

Submission status: Accepted

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

Submission status: Accepted

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


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


A, B, C, D = list(map(int, input().split()))
a_c = A // C if A % C == 0 else A // C + 1
b_c = B // C

abc = b_c - a_c + 1

a_d = A // D if A % D == 0 else A // D + 1
b_d = B // D

abd = b_d - a_d + 1

a_cd = A // (lcm(C, D)) if A % (lcm(C, D)) == 0 else A // (lcm(C, D)) + 1
b_cd = B // (lcm(C, D))
abcd = b_cd - a_cd + 1
print((B - A + 1) - abc - abd + abcd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Cw = C
Dw = D

if Cw < Dw:
    Cw, Dw = Dw, Cw
while Cw % Dw != 0:
    Cw, Dw = Dw, Cw % Dw

E = C * D // Dw

A -= 1

ans = (B - B // C - B // D + B // E) - (A - A // C - A // D + A // E)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def gcd(n, m):
	while m:
		n, m = m, n % m
	return n

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

if c == 1 or d == 1:
    print(0)
    exit()

if a == 1:
    div_a = 0
else:
    div_a = (a-1) // c + (a-1) // d - (a-1) // lcm(c, d)
div_b = b // c + b // d - b // lcm(c, d)

print(b - a + 1 - div_b + div_a)

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)
def f(x):
  return x//c + x//d - x//lcm(c,d)
def g(x):
  return x-f(x)
print(g(b)-g(a-1))

Submission status: Accepted

Solution code:
import math
from fractions import gcd
 
def number_calc(A,B,x):
    if A%x == 0:
        left = A//x
    else:
        left = A//x + 1
    right = B//x
    res = max(right-left+1,0)
    return res
 
A,B,C,D = map(int,input().split())
 
ans = B-A+1
ans -=number_calc(A,B,C)
ans -=number_calc(A,B,D)
lcm = (C*D)//gcd(C,D)
ans +=number_calc(A,B,lcm)
 
print(ans)

Submission status: Accepted

Solution code:
import copy
import fractions

inp = input()
# inp = "314159265358979323 846264338327950288 419716939 937510582"
inp = inp.split(" ")
a = int(inp[0])
b = int(inp[1])
c = int(inp[2])
d = int(inp[3])

h = c * d // fractions.gcd(c, d)
e = int(b // c) - int((a-1) // c)
f = int(b // d) - int((a-1) // d)
g = int(b // h) - int((a-1) // h)

print((b-a+1)-(e+f-g))

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

QC = 0 #Cで割り切れる
QD = 0 #Dで割り切れる
QCD = 0 #CとDで割り切れる

CD = lcm(C,D) #最大公約数

#約数の個数を求める
QC = (B // C) - (A // C)
if A % C == 0:
        QC += 1

QD = (B // D) - (A // D)
if A % D == 0:
        QD += 1

QCD = (B // CD) - (A // CD)
if A % CD == 0:
        QCD += 1

N = B-A+1
CorD = QC+QD-QCD

print(N-CorD)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import fractions

def gcd(a, b):
    return int(fractions.gcd(a, b))

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

class slist(list):
    def __init__(self, *args, **kw):
        list.__init__(self, *args, **kw)
        self.sort()

    def append(self, value):
        bisect.insort(self,value)

    def index_left(self, value):
        return bisect.bisect_left(self, value)

def calc(n, a, b):
    return n//a + n//b - n//lcm(a,b)
    #aa = (int(n/a))
    #bb = (int(n/b))
    #ab = (int(n/lcm(a,b)))
    #return int(aa + bb - ab)

if __name__ == '__main__':
    a, b, c, d = map(int, input().split())
    ans = calc(b, c, d) - calc(a - 1, c, d)
    print(b - a + 1 - ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import fractions

def gcd(a, b):
    return fractions.gcd(a, b)

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

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

if __name__ == '__main__':
    a, b, c, d = map(int, input().split())
    ## これで通った
    # num1 = b - calc(b,c,d)
    # num2 = (a-1) - calc(a-1, c,d)
    # print(num1-num2)

    ## これはとおらない
    ans = calc(b, c, d) - calc(a - 1, c, d)
    print(b - a + 1 - ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import fractions

def gcd(a, b):
    return fractions.gcd(a, b)

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

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

if __name__ == '__main__':
    a, b, c, d = map(int, input().split())
    ans = calc(b, c, d) - calc(a - 1, c, d)
    print(b - a + 1 - ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import fractions

def gcd(a, b):
    return fractions.gcd(a, b)

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

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

if __name__ == '__main__':
    a, b, c, d = map(int, input().split())
    ## これで通った
    # num1 = b - calc(b,c,d)
    # num2 = (a-1) - calc(a-1, c,d)
    # print(num1-num2)

    ## これはとおらない
    ans = calc(b, c, d) - calc(a - 1, c, d)
    print(int(b - a + 1 - ans))

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import fractions

def gcd(a, b):
    return fractions.gcd(a, b)

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

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

if __name__ == '__main__':
    a, b, c, d = map(int, input().split())
    num1 = b - calc(b,c,d)
    num2 = (a-1) - calc(a-1, c,d)
    # ans = calc(b, c, d) - calc(a - 1, c, d)
    # print(b - a + 1 - ans)
    print(num1-num2)