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:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    a, b, c, d = get_li()
    c_min = (a + c - 1) // c
    c_max = b // c
    if c == d:
        print(b - a + 1 - (c_max - c_min + 1))
        return
    d_min = (a + d - 1) // d
    d_max = b // d
    e = c * d // gcd(c, d)
    if c == e:
        print(b - a + 1 - (d_max - d_min + 1))
        return
    if d == e:
        print(b - a + 1 - (c_max - c_min + 1))
        return
    e_min = (a + e - 1) // e
    e_max = b // e
    print(b - a + 1 - (c_max - c_min + 1) - (d_max - d_min + 1) + (e_max - e_min + 1))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Accepted

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

from fractions import gcd

g = gcd(C,D)
l = C*D //g
k = l - (l//C) - (l//D) + 1 #l以下で、割り切れないのはk個
#print(g,l,k)
def n_not_devided_c_or_d(n):
  if n//l:
    return n_not_devided_c_or_d(n%l) + k * (n//l)
  return n - n//C - n//D

#print(n_not_devided_c_or_d(B))
#print(n_not_devided_c_or_d(A-1))

print(n_not_devided_c_or_d(B) - n_not_devided_c_or_d(A-1))

Submission status: Accepted

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

    return gcd(x,y%x)

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

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

ans1=(A-1)//C+(A-1)//D-(A-1)//(lcm(C,D))
ans2=(B)//C+(B)//D-(B)//(lcm(C,D))

ans3=(B-A+1)-(ans2-ans1)
print(ans3)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 6))

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

def main():
  a, b, c, d = map(int, input().split())
  divc = b//c - (a-1)//c
  divd = b//d - (a-1)//d
  abgcd = gcd(c, d)
  maxcd = (max(c, d) // abgcd) * min(c, d)
  print(b-a+1-divc-divd+(b//maxcd - (a-1)//maxcd))


if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

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


def LCM(a, b):
    return a * b // GCD(a, b)

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

cnt_c = b//c - (a-1)//c
cnt_d = b//d - (a-1)//d
cd = LCM(c, d)
cnt_cd = b//cd - (a-1)//cd

print(b-a+1-(cnt_c + cnt_d - cnt_cd))

Submission status: Accepted

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

def calc(x, k):
    return x // k


def all_calc(x):
    return x - (calc(x, c) + calc(x, d) - calc(x, c * d // gcd(c, d)))
print(all_calc(b) - all_calc(a - 1))

Submission status: Accepted

Solution code:
import fractions

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

C_count = B // C - (A - 1) // C
D_count = B // D - (A - 1) // D

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

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

can_divide = C_count + D_count - CD_count
print(B - A + 1 - can_divide)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return

#B
def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return

#C
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
from fractions import gcd

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

A = (a-1) // c + (a-1) // d - (a-1) // ((c * d) // gcd(c, d))
B = b // c + b // d - b // ((c * d ) // gcd(c, d))

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc131/tasks/abc131_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

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

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

    CD = C * D // gcd(max(C, D), min(C, D))
    # A 未満で C, D で割り切れる個数
    ac_div = (A - 1) // C
    ad_div = (A - 1) // D

    acd_div = (A - 1) // CD
    a_total = ac_div + ad_div - acd_div

    # B 以下で C, D で割り切れる個数
    bc_div = B // C
    bd_div = B // D

    bcd_div = B // CD
    b_total = bc_div + bd_div - bcd_div

    # B - A から割り切れる個数を引く
    ans = B - A + 1 - (b_total - a_total)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

A, B, C, D = map(int, raw_input().split())
def GCD(a, b):
	dummy1 = max(a, b)
	dummy2 = min(a, b)
	while True:
		dummy = dummy1 % dummy2
		dummy1 = dummy2
		dummy2 = dummy
		if dummy == 0:
			break
	return dummy1

ans = 0

LCM = C * D / GCD(C, D)

ans += B
ans -= B / D
ans -= B / C
ans += B / LCM
A -= 1
ans -= A
ans += A / D
ans += A / C
ans -= A / LCM
print ans

Submission status: Accepted

Solution code:
class FutureMath:
    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    def gcd_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.gcd(result, el)
        return result

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

    def lcm_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.lcm(result, el)
        return result

    def divisors(self, n):
        result = list()
        for i in range(1, n+1):
            if n % i == 0:
                result.append(i)
        return result


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

fm = FutureMath()


a, b, c, d = LI()
B = b - (b//c + b//d - b//fm.lcm(c, d))
A = a - (a//c + a//d - a//fm.lcm(c, d))
border = 1 - int((a % c == 0) or (a % d == 0))
print(B - A + border)

Submission status: Accepted

Solution code:
from fractions import gcd

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

lcm = c * d // gcd(c,d)
temp1 = b - b//c - b//d + b//lcm
temp2 = (a-1) - (a-1)//c - (a-1)//d + (a-1)//lcm

print(temp1 - temp2)

Submission status: Accepted

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

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

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

N = lcm(C,D)
A = A-1

s = A//C + A//D - A//N
t = B//C + B//D - B//N

print(B-t - (A-s))

Submission status: Accepted

Solution code:
#C問題
A,B,C,D = map(int,input().split())
#gcd(二つの数)
def gcd(GCD1,GCD2):
    x = min(GCD1,GCD2)
    y = max(GCD1,GCD2)
    if y%x == 0:
        return x
    else:
        return gcd(x,y%x)
GCD = gcd(C,D)
per = C*D//GCD
def f(n,a,b):
    gab = gcd(a,b)
    perab = a*b//gab
    ret = n-(n//a)-(n//b)+(n//perab)
    return int(ret)
print(f(B,C,D)-f(A-1,C,D))

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

print(b - a - (cnt0B - cnt0A))

Submission status: Accepted

Solution code:
import fractions

def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    a,b,c,d=map(int, input().split())
    x0 = b // c - (a-1) // c
    x1 = b // d - (a-1) // d
    tmp = c*d//fractions.gcd(c, d)
    x2 = b // tmp - (a-1) // tmp
    print(b-a+1-x0-x1+x2)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(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)

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

print(ans-cn-dn+cdn)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D=map(int,input().split())
#CとDのどちらかで割り切れる
#=(Cで割り切れる)+(Dで割り切れる)-(lcm(C,D)で割り切れる)
L=(C*D)//gcd(C,D)
#(i-1)<A/C<=i
#i*C<=B<(i+1)C
i=(B//C)-(-((-A)//C))+1
j=(B//D)-(-((-A)//D))+1
k=(B//L)-(-((-A)//L))+1
print(B-A+1-(i+j-k))

Submission status: Accepted

Solution code:
A,B,C,D = [ int(it) for it in 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)
  
R = lcm(C,D)

def chk(V):
  return V - (V//C) - (V//D) + (V//R)

print ( chk(B) - chk(A-1) )

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):
    g = gcd(a, b)
    g_a = a // g
    g_b = b // g
    return g_a * g_b * g

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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


def solve(A: int, B: int, C: int, D: int):
    U = B-A+1
    cdivnum = B//C - (A-1)//C
    ddivnum = B//D - (A-1)//D
    cd = C*D//GCD(C, D)
    cddivnum = B//cd - (A-1)//cd
    print(U-cdivnum-ddivnum+cddivnum)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

A, B, C, D = nl()

c_total = B // C - (A - 1) // C
d_total = B // D - (A - 1) // D

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

print(B - A + 1 - (c_total + d_total - cd_total))

Submission status: Accepted

Solution code:
from fractions import gcd

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

def f(a):
    return a - (a // c + a // d - a // (c * d // gcd(c, d)))

print(f(b) - f(a - 1))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

a, b, c, d = na()

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

def cou(b, c, d):
    g = gcd(c, d)
    return b - b//c - b//d + b//(c//g*d)

print(cou(b, c, d) - cou(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)

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

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

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

Submission status: Accepted

Solution code:
#C
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
def count(a,b,k):
    cnt=b//k-a//k
    if a%k==0:
        cnt+=1
    return cnt

a,b,c,d=map(int,input().split())
l=lcm(c,d)
print(b-a+1-count(a,b,c)-count(a,b,d)+count(a,b,l))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(A: int, B: int, C: int, D: int):
    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a % b)
    g = gcd(C, D)
    c = B // C - (A - 1) // C
    d = B // D - (A - 1) // D
    cd = B // (C * D // g) - (A - 1) // (C * D // g)
    #print(c, d, cd)
    ret = B - A - c - d + cd + 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


lcm = lambda a, b: a * b // gcd(a, b)


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

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


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

from fractions import gcd

lcm = (c * d) // gcd(c, d)
x = b - (b // c + b // d - b // lcm)

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

print(x - y)

Submission status: Accepted

Solution code:
import fractions as frac
a,b,c,d=map(int,input().split())
e=frac.gcd(c,d)
f=(c*d)//e
x=b//c
y=b//d
z=b//f
u=(a-1)//c
v=(a-1)//d
s=(a-1)//f
num1=(b-(x+y-z))
num2=((a-1)-(u+v-s))
print(num1-num2)

Submission status: Accepted

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


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


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


LCM = lcm(C, D)


def calc(n):
    div_c = n // C
    div_d = n // D
    div_c_d = n // LCM
    return n - div_c - div_d + div_c_d


print(calc(B) - calc(A - 1))

Submission status: Accepted

Solution code:
from fractions import gcd

def count_multiples(a,b,m):
    a = ((a-1)//m + 1)
    b = b//m
    return b-a+1

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

Submission status: Accepted

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

def f(n, x, y):
    m = 0
    m += n // x
    m += n // y
    m -= n // (x // gcd(x, y) * y)
    return n - m

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

A,B,C,D=rl()

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

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

CD = lcm(C,D)

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x

lcm = lambda a, b: a * b // gcd(a, b)

def real_main():
    a, b, c, d = read_int_array()
    def aux(x):
        n1 = x // c
        n2 = x // d
        n3 = x // (lcm(c, d))
        return x - n1 - n2 + n3

    print(aux(b) - aux(a-1))


def solve():
    pass


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs, answers):
    total, wrong = 0, 0
    for args, test_ans in zip(inputs, answers):
        ans = solution(*deepcopy(args))
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


# This mergesort can be like 7 times faster than build in sort
# (for stupid reasons)
def mergesort(A, key=lambda x: x, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if key(C[A[i]]) > key(C[A[i ^ 1]]):
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if key(C[A[i]]) > key(C[A[j]]):
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

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

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]

# endregion

if __name__ == "__main__":
    main()

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)

def count(X, a, b):
    return X//a + X//b - X//lcm(a, b)

print((B - A + 1) + count(A-1, C, D) - count(B, C, D))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#n = int(input())
#a = [int(i) for i in input().split()]
from fractions import gcd 



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

def res(n):#n以下
    return n - n//c - n//d + n//(c*d//gcd(c,d))

print(res(b) - res(a-1))

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

cnt_b = b // c + b // d - b // lcm(c, d)
cnt_a = (a - 1) // c + (a - 1) // d - (a - 1) // lcm(c, d)

print(b - a + 1 - (cnt_b - cnt_a))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    A, B, C, D = MI()
    lcm = C * D // gcd(C, D)
    ans = B-(B // C + B // D - B // lcm)
    ans -= (A-1)-((A-1)//C + (A-1)//D - (A-1)//lcm)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# from math import gcd
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from itertools import combinations as comb
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)
def y(f):
    if f:
        print('Yes')
    else:
        print('No')
def Y(f):
    if f:
        print('YES')
    else:
        print('NO')


a,b,c,d = map(int,input().split())
g = gcd(c, d)
l = c * d // g

def f(p, q):
    return p // q

res = b - a + 1
res -= f(b, c) - f(a - 1, c)
res -= f(b, d) - f(a - 1, d)
res += f(b, l) - f(a - 1, l)

print(res)

Submission status: Accepted

Solution code:
import fractions

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

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

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


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

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
if a%c==0:
  countc1=(a//c)-1
else:
  countc1=a//c
countc2=b//c
if a%d==0:
  countd1=(a//d)-1
else:
  countd1=a//d
countd2=b//d
def gcd(n,m):
  a=max(n,m)
  b=min(n,m)
  while b!=0:
    a,b=b,a%b
  return a
e=c*d//gcd(c,d)
if a%e==0:
  counte1=(a//e)-1
else:
  counte1=a//e
counte2=b//e
print(b-a+1+countc1+countd1-counte1-countc2-countd2+counte2)

Submission status: Accepted

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

a,b,c,d=map(int,input().split())
ans1=b//c-(a//c)
if(a%c==0):
	ans1+=1
ans2=b//d-(a//d)
if(a%d==0):
	ans2+=1

lcm=(c*d)//(gcd(min(c,d),max(c,d)))
ans3=b//lcm-(a//lcm)
if(a%lcm==0):
	ans3+=1
print(b-a+1-(ans1+ans2-ans3))

Submission status: Accepted

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

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

cs = B//C-(A-1)//C
ds = B//D-(A-1)//D

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

es = B//E-(A-1)//E

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from fractions import gcd

def main():
    A, B, C, D = LI()
    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)
    return ans

print(main())