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(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義

il = list(map(int, input().split()))

a = il[0]-1
b = il[1]
c = il[2]
d = il[3]

numa =  a- a//c - a//d + a//(c*d//gcd(c,d))
numb =  b- b//c - b//d + b//(c*d//gcd(c,d))

print(numb-numa)

Submission status: Accepted

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

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

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

a_cd = (A - 1) // (lcm)
b_cd = B // (lcm)

a_c = (A - 1) // C
a_d = (A - 1) // D
b_c = B // C
b_d = B // D

a = a_c + a_d - a_cd
b = b_c + b_d - b_cd

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

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))

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

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

def num_div(k,s):
    return s // k

a,b,c,d = words(int)

cd_lcm = lcm(c,d)

n_div_till_b = num_div(c,b) + num_div(d,b) - num_div(cd_lcm, b)
n_div_till_am1 = num_div(c,a-1) + num_div(d,a-1) - num_div(cd_lcm,a-1)

ans = (b-a+1) - n_div_till_b + n_div_till_am1

print(ans)

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter 
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


# initialize variables and set inputs
#initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6

# # set test data
# sys.stdin = open('sample.txt') # for test

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())

# set inputs
a, b, c, d = R()
if c == d:
    print(b-a+1-(b//c - (a-1)//c))
else:
    print(b - a + 1 - (b//c - (a-1)//c + b//d - (a-1)//d - (b//(lcm(c,d)) - (a-1)//(lcm(c,d)))))


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

Submission status: Accepted

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

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

def gcd(x, y):
    if x < y:
        x, y = y, x
    if x % y == 0:
        return y
    return gcd(y, x % y)
    
s = C * D // gcd(C, D)

a = (A - 1) // C + (A - 1) // D - (A - 1) // s
b = B // C + B // D - B // s

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(A: int, B: int, C: int, D: int):
    def doit(N):
        a = A
        if a % N != 0:
            a += (N - A % N)
        return (B - a) // N + 1
    cs = doit(C)
    ds = doit(D)

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

    return (B - A + 1) - cs - ds + es


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    result = solve(A, B, C, D)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b,c,d=[int(k) for k in input().split(" ")]

def bezout(a,b) :              # retourne (g,u,v) tel que g = a*u + b*v et g = pgcd(a,b)
    if b == 0 : return (a,1,0)
    q = a // b 
    r = a % b
    (g,u1,v1) = bezout(b,r)    
    return (g,v1,u1-q*v1)      # joli algo :-)



def nbdb(n,d):
    return n//d

def nbdbi(l,r,d):
    return nbdb(r,d)-nbdb(l-1,d)

def solve():
    g=bezout(c,d)[0]
    return b-a+1-nbdbi(a,b,c)-nbdbi(a,b,d)+nbdbi(a,b,c*d//g)

print(solve())

Submission status: Accepted

Solution code:
A, B, C, D = [int(c) for c in input().split()]

p, q = max(C, D), min(C, D)
while q: p, q = q, p%q
E = C*D//p

Cmult_ge_A = A if A%C==0 else A+C-A%C
Dmult_ge_A = A if A%D==0 else A+D-A%D
Emult_ge_A = A if A%E==0 else A+E-A%E

nC = (B-Cmult_ge_A)//C+1
nD = (B-Dmult_ge_A)//D+1
nE = (B-Emult_ge_A)//E+1

print(B-A+1-nC-nD+nE)

Submission status: Accepted

Solution code:
def bal(c,d,m,n):
  if c < d:
    return bal(d,c,m,n)
  else:
    if c % d == 0:
      return m*n/d
    else:
      return bal(d,c%d,m,n)

s = input().split()
a = int(s[0])
b = int(s[1])
c = int(s[2])
d = int(s[3])
e = int(bal(c,d,c,d))
n = b - (b//c) - (b//d) + (b // e)
m = (a-1) - ((a-1) // c) - ((a-1) // d) + ((a-1) // e)
print(n-m)

Submission status: Accepted

Solution code:
from fractions import gcd
#[N,K] = list(map(int,input().split()))
#A = list(map(int,input().split()))
#[A,B,C,D] = list(map(int,input().split()))
[A,B,C,D] = list(map(int,input().split()))
def lcm(x, y):
    return (x * y) // gcd(x, y)
x_c = (B//C) - ((A-1)//C)
x_d = (B//D) - ((A-1)//D)
x_cd = (B//lcm(C,D)) - ((A-1)//lcm(C,D))
ans = (B - A + 1) - (x_c + x_d -x_cd)
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

a, b, c, d = LI()
a = a-1

cd = int(c * d / gcd(c, d))
cs = b // c - a // c
ds = b // d - a // d
cds = b // (cd) - a // (cd)
print(b - a - cs - ds + cds)

Submission status: Accepted

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

Submission status: Accepted

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

def gcd_strategy():
    import math
    import fractions
    return math.gcd if hasattr(math, "gcd") else fractions.gcd
gcd = gcd_strategy()

cd=c*d//gcd(c,d)
countcd=(b//cd)-((a-1)//cd)
print(1+b+countcd-(a+countc+countd))

Submission status: Accepted

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

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

count_a = a - (a//c + a//d - a//(l))
count_b = b - (b//c + b//d - b//(l))

print(count_b-count_a)

Submission status: Accepted

Solution code:
def c_anti_division(A, B, C, D):
    from fractions import gcd

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

    def bai(n, b):
        """1からnまでのbの倍数の個数"""
        return (n - 1 + 1) // b
    ans = ((B - A + 1)
           - ((bai(B, C) + bai(B, D) - bai(B, lcd))
              - (bai(A - 1, C) + bai(A - 1, D) - bai(A - 1, lcd))))
    return ans

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

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

tot = b - a + 1
e = c*d//gcd(c,d)
ans = tot - (b//c-(a-1)//c) - (b//d-(a-1)//d) + (b//e-(a-1)//e)
print(int(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 f(X, C, D):
    return X - X//C - X//D + X//lcm(C,D)


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

    ans = f(B, C, D) - f(A-1, C, D)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def func(x, y):
    return x//y

a, b, c, d = list(map(int, input().split()))
n = b-a+1
candivide1 = func(b,c) - func(a-1,c)
candivide2 = func(b,d) - func(a-1,d)
cd = c*d // gcd(c,d)
both = func(b, cd) - func(a-1, cd)
ans = n - candivide1 - candivide2 + both
print(ans)

Submission status: Accepted

Solution code:
A,B,C,D = map(int,input().split())
def gcd(a,b):
    if b == 0:
        return a 
    else :
        a_ = b
        b_ = a % b
        return gcd(a_,b_)

def lcm(a,b):
    return a*b//gcd(a,b)
E = lcm(max(C,D),min(C,D))
#A～BでCで割り切れるものの個数
if A % C == 0 :
    p = B//C - A//C + 1
else :
    p = B//C - A//C
#A~BでDで割り切れるものの個数
if A % D == 0 :
    q =B//D - A//D + 1
else:
    q = B//D - A//D 
#両方で割れるものの個数
if A % E == 0 :
    r = B//E - A//E + 1
else :
    r = B//E - A//E 

ans = B - A + 1 - (p + q - r)
print(ans)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = [int(x) for x in input().split()]
p = B//C - (A-1)//C
q = B//D - (A-1)//D
g = C*D // fractions.gcd(C, D)
r = B//g - (A-1)//g
cnt = B-A+1 - (p+q-r)
print(cnt)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def mul_count(min_val, max_val, div_val):
    return max_val // div_val - (min_val - 1) // div_val

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

c_cnt = mul_count(A, B, C)
d_cnt = mul_count(A, B, D)
cd_cnt = mul_count(A, B, lcm(C, D))
print(B - A - (c_cnt + d_cnt - cd_cnt) + 1)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a%b == 0 :
        return b
    return gcd(b, a%b)
a,b,c,d=[int(_) for _ in input().split()]
nac=(a-1) - (a-1)//c
nbc=b - b//c
nad=(a-1) - (a-1)//d
nbd=b - b//d
lcm=c*d//gcd(c,d)

nacd=(a-1) - (a-1)//lcm
nbcd=b - b//lcm
print(nbc-nac + nbd-nad -nbcd+nacd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys

def gcd(aa,bb):
    aa, bb = max(aa,bb), min(aa,bb)
    while bb!=0:
        aa,bb=bb,aa%bb
    return aa

def f(n,m):
    nm = n % m
    if nm==0: return n
    else: return n + m - nm
#
a,b,c,d = [ int(x) for x in sys.stdin.readline().split() ]
cd = c * d // gcd(c,d)

# nc
aa = f(a,c)
if aa>b: nc=0
else: nc= (b-aa)//c + 1

# nd
aa = f(a,d)
if aa>b: nd=0
else: nd= (b-aa)//d + 1

# ncd
aa = f(a,cd)
if aa>b: ncd= 0
else: ncd= (b-aa)//cd + 1
#
print( b-a+1 - ( nc + nd - ncd ) )

Submission status: Accepted

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

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

koubai = lcm(c, d)

a -= 1
x1 = a // c
x2 = a // d
x3 = a // koubai

y1 = b // c
y2 = b // d
y3 = b // koubai

ans = b - a - ((y1+y2-y3) - (x1+x2-x3))

print(ans)

Submission status: Accepted

Solution code:
A,B,C, D = map(int, input().split())
def gcd(n, m ):
    if n%m == 0:
        return m
    else:
        return gcd(m, n%m)
gcdCD = gcd(C, D)
lcmCD = int(C * D /gcdCD)
def count(start , end , n):
    return end//n -(start-1)//n
numC = count(A, B, C)
numD = count(A, B, D)
numCD = count(A,B, lcmCD)
warikireCD = numC + numD - numCD
print(B- A + 1 - warikireCD)

Submission status: Accepted

Solution code:
import fractions

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


def baisuu(suuji, shita, ue):
    saishou, shouamari = divmod(shita, suuji)
    saidai, daiamari = divmod(ue, suuji)
    ans = saidai - saishou
    if shouamari == 0:
        ans += 1
    return ans


cbai = baisuu(C, A, B)
dbai = baisuu(D, A, B)
koubai = C * D // fractions.gcd(C, D)
koubaibai = baisuu(koubai, A, B)

print(B - A + 1 - cbai - dbai + koubaibai)

Submission status: Accepted

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


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


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


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





if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

bm = b // m
am = (a-1) // m
aa = (bc - ac) + (bd - ad) - (bm - am)

print(b-(a-1)-aa)

Submission status: Accepted

Solution code:
def gcd(x, y):

   while(y):
       x, y = y, x % y

   return x
a,b,c,d = map(int,input().split())
lcm = (c*d)//gcd(c,d)
l = b-a+1
if(a%c!=0):
    p = b//c-a//c
else:
    p = b//c-a//c+1
if(a%d!=0):
    q = b//d-a//d
else:
    q = b//d-a//d+1
if(a%lcm!=0):
    r = b//lcm-a//lcm
else:
    r = b//lcm-a//lcm+1
print(l-(p+q-r))

Submission status: Accepted

Solution code:
from fractions import gcd
inf = input().split()
A = int(inf[0])
B = int(inf[1])
C = int(inf[2])
D = int(inf[3])

num = B-A+1
target = B
X = C*D//gcd(C,D)

total = B//C + B//D - B//X
lim = (A-1)//C + (A-1)//D - (A-1)//X
print(num-total+lim)

Submission status: Accepted

Solution code:
a,b,N,M = map(int,input().split())
n = N
m = M
while m != 0:
  mt = n%m
  n = m
  m = mt
g = N*M//n
mass = g//N + g//M - 1
bq = b // g
br = b % g
bsc = mass * bq
bsc += br // N
bsc += br // M
aq = (a-1) // g
ar = (a-1) % g
asc = mass * aq
asc += ar // N
asc += ar // M
print(b-a-bsc+asc+1)

Submission status: Accepted

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

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

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

quotient_c = b // c - (a - 1) // c
quotient_d = b // d - (a - 1) // d
quotient_lcm = b // lcm - (a - 1) // lcm

print(b - a + 1 - quotient_c - quotient_d + quotient_lcm)

Submission status: Accepted

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

def solve():
  A, B, C, D = map(int, input().split())
  A = A - 1
  CD = C * D // gcd(C, D)
  num_C = (B // C) - (A // C)
  num_D = (B // D) - (A // D)
  num_CD = (B // CD) - (A // CD)
  return B - A - num_C - num_D + num_CD

print(solve())

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

B_C = B // C
B_D = B // D
B_C_D = B // lcm(C, D)

A_C = (A - 1) // C
A_D = (A - 1) // D
A_C_D = (A - 1) // lcm(C, D)

B_div = B_C + B_D - B_C_D
A_div = A_C + A_D - A_C_D



print(B - A + 1 - (B_div - A_div))

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)

E = lcm(C, D)

# B以下
ans_b_c = (B // C) + (B // D) - (B // E)
ans_b = B - ans_b_c
# A未満
ans_a_c = ((A - 1) // C) + ((A - 1) // D) - ((A - 1) // E)
ans_a = (A - 1) - ans_a_c

ans = ans_b - ans_a
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from fractions import gcd

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C, D):
    ac = (A-1)//C
    ad = (A-1)//D
    acd = (A-1)//(C * D // gcd(C, D))
    bc = B//C
    bd = B//D
    bcd = B//(C * D // gcd(C, D))
    R = B - (bc + bd - bcd)
    L = (A-1 - (ac + ad - acd))
    return  R - L


def main():
    A, B, C, D = read_int_n()
    print(slv(A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
e = fractions.gcd(c,d)
k = int(c*d/e)
if a%c == 0:
    if a%d == 0:
        f = (b//c) - (a//c) + 1
        g = (b//d) - (a//d) + 1
        h = (b//k) - (a//k) + 1
    else:
        f = (b//c) - (a//c) + 1
        g = (b//d) - (a//d)
        h = (b//k) - (a//k)
else:
    if a%d == 0:
        f = (b//c) - (a//c)
        g = (b//d) - (a//d) + 1
        h = (b//k) - (a//k)
    else:
        f = (b//c) - (a//c)
        g = (b//d) - (a//d)
        h = (b//k) - (a//k)
print(b-a+1-f-g+h)

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:
from fractions import gcd

A, B, C, D = map(int, input().split())
res = B - A + 1
CD = (C // gcd(C, D)) * D
# print(CD)
div_C = B // C - (A - 1) // C
# print(div_C)
div_D = B // D - (A - 1) // D
# print(div_D)
div_CD = B // (CD) - (A - 1) // (CD)

ans = res - (div_C + div_D - div_CD)
print(ans)

Submission status: Accepted

Solution code:
import fractions as fr

A, B, C, D = map(int, input().split())
lcm = C * D // fr.gcd(C, D)
ans = B - A + 1
ans -= B // C - (A-1) // C
ans -= B // D - (A-1) // D
ans += B // lcm - (A-1) // lcm
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())

#0からわりきれる
x0 = B//C
y0 = B//D
z0 = B//lcm(C,D)

all0 = x0+y0-z0
all0 = B-all0

#それ以下から
x1 = (A-1)//C
y1 = (A-1)//D
z1 = (A-1)//lcm(C,D)
all1 = x1+y1-z1
all1 = A-1-all1


print(all0-all1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

a,b,c,d = na()
a-=1

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

e = lcm(c,d)

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

acd = a//e
bcd = b//e

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

print(b-a-loo)

Submission status: Accepted

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


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


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

# B以下で割り切れる
UB_C = B // C
UB_D = B // D
UB_CD = B // lcm(C, D)

UB = B - (UB_C + UB_D - UB_CD)

# A以下で割り切れる
UA_C = A // C
UA_D = A // D
UA_CD = A // lcm(C, D)

UA = A - (UA_C + UA_D - UA_CD)

ans = UB - UA

if A % C != 0 and A % D != 0:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import  fractions

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


def do():
    A,B,C,D =  list(map(int,input().split(" ")))
    CD = lcm(C,D)
    A1 = A- 1
    ans = (B//C + B//D - B//CD) - (A1//C + A1//D - A1//CD)
    ans = (B-A+1) - ans
    print(ans)

if __name__ == "__main__":
    do()

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
# A//C
ac = A // C # 4
bc = B // C # 2
ad = A // D # 3
bd = B // D # 1


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

cd = C * D // gcd(C,D)
acd = A // cd
bcd = B // cd

res = B - A + 1 - bc + ac - bd + ad + bcd - acd
 

if A % C == 0:
    res -= 1
if A % D == 0:
    res -= 1
if A % cd == 0:
    res += 1

print(res)

Submission status: Accepted

Solution code:
import fractions

def count_div(x, v, w):
  return w // x - (v - 1) // x

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

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())
mabigki = 0
mabigki +=  B//C + B//D - B//(lcm(C,D))
b = A - 1
mabigki -=  b//C + b//D - b//(lcm(C,D))
ans = B-A+1 -mabigki
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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


if __name__ == "__main__":
    [a, b, c, d] = li()
    lcm = c * d // gcd(c, d)
    # print(lcm)
    # print(multiplier_num(a, b, c))
    # print(multiplier_num(a, b, d))
    # print(multiplier_num(a, b, lcm))
    answer = b - a + 1 - multiplier_num(a, b, c) - multiplier_num(a, b, d) + multiplier_num(a, b, lcm)
    print(answer)

# cでもdでも割り切れない
# 全体からcで割り切れる個数を引き、dで割り切れる個数を引くと
# 　cでもdでも割り切れる個数を引きすぎるので足して戻す
# a以上b以下でxで割り切れる個数
# 　b//x - a//x

Submission status: Accepted

Solution code:
import fractions

def get_num(N, num1, num2):
    lcm = num1 * num2 // fractions.gcd(num1, num2)
    return N - N // num1 - N // num2 + N // lcm


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

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

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

CD = lcm(C,D)
cnta = (A//C) + (A//D) - (A//(CD))
cntb = (B//C) + (B//D) - (B//(CD))

print(B - A - (cntb - cnta))

Submission status: Accepted

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

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

def div(a, b):
    return a // b

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

ans = 0
ans += div(B, C)
ans -= div(A - 1, C)
# print("#", ans)
ans += div(B, D)
ans -= div(A - 1, D)
# print("#", ans)
#
E = (C * D) // gcd(C, D)
ans -= div(B, E)
ans += div(A - 1, E)
# print("#", ans)

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

Submission status: Accepted

Solution code:
import fractions

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

S = 1 + B - A
S1 = (B // C) - ((A-1) // C) 
S2 = (B // D) - ((A-1) // D)
S3 = (B // F) - ((A-1) // F)
print(S - S1 - S2 + S3)

Submission status: Accepted

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

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

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


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


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

remain = (B - A + 1) - (nC + nD - nLCM)
print(remain)

Submission status: Accepted

Solution code:
def sks(c,d):
    if c==0:
        return(d)
    else:
        return(sks(d%c,c))
a,b,c,d=list(map(int,input().split()))
s=sks(min(c,d),max(c,d))
t=int(c*d//s)
e=b-b//c-b//d+b//t
f=(a-1)-(a-1)//c-(a-1)//d+(a-1)//t
print(int(e-f))

Submission status: Accepted

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

Cok=b//c-(a-1)//c
Dok=b//d-(a-1)//d
CDok=b//lcm(c,d)-(a-1)//lcm(c,d)
print(b-a+1-Cok-Dok+CDok)

Submission status: Accepted

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

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

cd = (c * d) // gcd(c, d)
a_c = (a-1) // c
b_c = b // c
a_d = (a-1) // d
b_d = b // d
a_cd = (a-1) // cd
b_cd = b // cd

print(b - a + 1 - (b_c - a_c) - (b_d - a_d) + (b_cd - a_cd))

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
CD = C * D // gcd(C, D)
cd = B // CD - (A - 1) // CD
print((B - A) - (c + d - cd) + 1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import collections
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

A,B,C,D = IL()

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

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

Submission status: Accepted

Solution code:
import fractions

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

A, B, C, D = getlist()

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

if A % C == 0:
	cx = int(B // C - A // C + 1)
else:
	cx = int(B // C - A // C)
if A % D == 0:
	dx = int(B // D - A // D + 1)
else:
	dx = int(B // D - A // D)

if A % x == 0:
	cdx = int(B // x - A // x + 1)
else:
	cdx = int(B // x - A // x)

print(B - A + 1 - cx - dx + cdx)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
A, B, C, D = list(map(int, input().split()))
kou = (C * D) // gcd(C, D)
a1 = (A-1)//C
a2 = (A-1)//D
a3 = (A-1)//(kou)
a = (A-1)-(a1+a2-a3)
b1 = B//C
b2 = B//D
b3 = B//(kou)
b = B-(b1+b2-b3)
print(b-a)

Submission status: Accepted

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

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

def get(x):
    return x - x // C - x // D + x // ((C*D)//gcd(C, D))

print(get(B)-get(A-1))

Submission status: Accepted

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

a, b, c, d = map(int, input().split())
x2 = b // c
x1 = (a - 1) // c
y2 = b // d
y1 = (a - 1) // d
t = c * d // gcd(c, d)
z2 = b // t
z1 = (a - 1) // t
print(b - a + 1 - (x2 - x1) - (y2 - y1) + (z2 - z1))

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools

def lcm(m,n):
    p=max(m,n)
    q=min(m,n)
    if p % q == 0:
        return q
    else:
        return lcm(q,p%q)



# いくつか入力
a,b,c,d = (int(i) for i in input().split())  

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

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