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:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()
    if ans is not None:
        print(ans)


def solve():
    A, B, C, D = iip(False)

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

    cc = soinsuu_bunkai(C)
    dd = D
    for ccc in cc:
        if dd % ccc == 0:
            dd //= ccc
    CD = dd * C
    #print(CD)

    c = B//CD - (A-1)//CD

    #print(a, b, c)
    return B-A+1 -a-b+c



#####################################################ライブラリ集ここから

def iip(listed=True, num_only=True):
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def sort_tuples(l, index):
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):
    if index >= len(l):
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):
    return "".join(sorted(s))


def iip_ord(startcode="a"):
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)


def bitall(N):
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret


def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side="left"):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_=mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions

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

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

p = b//c - (a-1)//c
q = b//d - (a-1)//d
r = b//(f2) - (a-1)//(f2)

print((b-a+1) - (p+q-r))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def q3():
    """ C - Anti-Division """
    from fractions import gcd  # 3.4.3ではmath.gcdは無い
    A,B,C,D = (int(i) for i in input().split())

    def lcm(x, y):
        """ 最小公倍数を求める """
        return (x * y) // gcd(x, y)

    num_C = B // C - (A - 1) // C  # Cで割り切れる個数
    num_D = B // D - (A - 1) // D  # Dで割り切れる個数
    lcm_CD = lcm(C, D)
    num_CD = B // lcm_CD - (A - 1) // lcm_CD  # CとDの最小公倍数で割り切れる個数
    num_all = num_C + num_D - num_CD  # 全ての割り切れる個数
    ans = B - A + 1 - num_all
    print(ans)


if __name__ == '__main__':
    q3()

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
def l(x,y):
    return (x*y)//gcd(x,y)
U = b-a+1
s1 = b//c - (a-1)//c
s2 = b//d - (a-1)//d
s3 = b//l(c,d) - (a-1)//l(c,d)
print(U-(s1+s2-s3))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

lcm = (C * D)//fractions.gcd(C, D)
area = B - A + 1
Carea = (B // C - (A-1) // C)
Darea = (B // D - (A-1) // D)
CDarea = (B//lcm - (A-1)//lcm)

print(area - (Carea+Darea-CDarea))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def cm_between(a, b, p):
    a_mod = a % p
    b_mod = b % p
    if b - a < p and 0 < a_mod <= b_mod:
        return 0
    elif a_mod == 0:
        return ((b - b_mod - a) // p + 1)
    else:
        return (((b - b_mod) - (a + p - a_mod)) // p + 1)

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

Submission status: Accepted

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))

a,b,c,d = load_list()

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



print((b-a+1) - (f(b, c, d) - f(a-1, c, d)))

Submission status: Accepted

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

# 方針
# 入力例1をよくみてみる。
# 1 2 3 4 5 6 7 8 9 10 11... に対して範囲[ 4, 9 ]の間で2の倍数を(),3の倍数を{}で示す
# 1 (2) {3} | (4) 5 {(6)} 7 (8) {9} | (10) 11.. となる。
# 範囲[1,9]の間の倍数で"ない"ものの個数と範囲[1,3]の間の倍数で"ない"ものの個数がわかれば良いことがわかる

# 範囲[ 1, upper ]の倍数で"ない"ものの個数
# Cの倍数とDの倍数を足してCDの最小公倍数を引く。それらが倍数で"ある"ものの個数。
# よって戻り値は全体から倍数で"ある"ものの個数を引く
def get_non_div_cnt_with_range( upper ):
  num_of_range_with_C  = ( upper // C )
  num_of_range_with_D  = ( upper // D )
  num_of_range_with_CD = ( upper // ( C * D // gcd( C, D ) ))
  return upper - ( num_of_range_with_C + num_of_range_with_D - num_of_range_with_CD )

upper_limit = B
lower_limit = A - 1
  
print( get_non_div_cnt_with_range( upper_limit ) - get_non_div_cnt_with_range( lower_limit ) )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

a_mod_c = a%c
if a_mod_c == 0:
  a_mod_c = c
a_c = a + (c - a_mod_c)
count_c = (b - a_c)//c + 1

a_mod_d = a%d
if a_mod_d == 0:
  a_mod_d = d
a_d = a + (d - a_mod_d)
count_d = (b - a_d)//d + 1

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

a_mod_lcm = a%lcm
if a_mod_lcm == 0:
  a_mod_lcm = lcm
a_lcm = a + (lcm - a_mod_lcm)
count_lcm = (b - a_lcm)//lcm + 1

ans = (b-a+1) - (count_d + count_c - count_lcm)

print(int(ans))

Submission status: Accepted

Solution code:
import fractions
#なぜかWA
"""
A,B,C,D = list(map(int, input().split()))
cc = int(B/C) - int((A-1)/C)
dd = int(B/D) - int((A-1)/D)
cd = int(C*D / fractions.gcd(C,D))
ee = int(B/cd) - int((A-1)/cd)
U = B-A+1
print(U - (cc + dd - ee))
"""
#解説読んだ
#なんで通らなくぁｗせｄｒｆｔｇｙふじこｌｐ
#?????????????????
A,B,C,D = list(map(int, input().split()))
def y(n, c, d):
    cd = c // fractions.gcd(c,d) * d
    cc = n//c
    dd = n//d
    ee = n//cd
    return n - cc - dd + ee

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

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  A, B, C, D = map(int, readline().split())
  
  def F(x):
    y = x//C
    y += x//D
    lcm = C*D//gcd(C,D)
    y -= x//lcm
    return x-y
  ans = F(B) -F(A-1)
  print(ans)
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
"""
ans: B以下の整数から条件を満たす個数　 - A-1以下の整数から条件を満たす個数
X以下の整数から条件： X - X//c -X//d + X//lcm(c,d)
"""
def count(X, t):
    return X//t
cd = c * d // gcd(c, d)
b_under = b - count(b, c) - count(b, d) + count(b, cd)
a_under = a-1 - count(a-1, c) - count(a-1, d) + count(a-1, cd)

print( b_under - a_under )

Submission status: Accepted

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

bc = B // C 
bd = B // D
bcd = B // (C*D//fractions.gcd(C, D))
ans = B- (bc + bd - bcd)
ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) //(C*D//fractions.gcd(C, D))
ans2=  A-1 - (ac + ad - acd)
ans = ans - ans2
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

a,b,c,d = map(int,input().split())
a -= 1
def div(m,n):
	return m // n

ans_a = a - div(a,c) - div(a,d) + div(a,c*d//gcd(c,d))
ans_b = b - div(b,c) - div(b,d) + div(b,c*d//gcd(c,d))

print(ans_b - ans_a)

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)


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


a, b, c, d = map(int, input().split())
a -= 1
print(b-a+sum(map(f, [(b, a, c), (b, a, d), (a, b, lcm(c, d))])))

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
from fractions import gcd

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

lcm = c * d // gcd(c, d)
a -= 1

under_b = b - (b//c + b//d - b//lcm)
under_a = a - (a//c + a//d - a//lcm)

answer = under_b - under_a
print(answer)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
def div_num(a, b, c):
    if (a%c)==0:
        return (b//c)-(a//c)+1
    else:
        return (b//c)-(a//c)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
XC = div_num(A, B, C)
XD = div_num(A, B, D)
XCD = div_num(A,B,int((C*D)/gcd(C,D)))
print(B-A+1-(XC+XD-XCD))

Submission status: Accepted

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

Submission status: Accepted

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

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
div_c = B // C
div_d = B // D
cd = lcm(C, D)
div_cd = B // cd
B_ = B - (div_c + div_d - div_cd)

A -= 1
div_c2 = A // C
div_d2 = A // D
div_cd2 = A // cd
A_ = A - (div_c2 + div_d2 - div_cd2)

print(B_ - A_)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

c_div = B//C - (A-1)//C
d_div = B//D - (A-1)//D
g = C*D // gcd(C, D)
cd_div = B//g - (A-1)//g
tot = B - A + 1
print(tot - c_div - d_div + cd_div)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    a,b,c,d = map(int, input().split())
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    a -= 1
    x = a - a//c - 1 - a//d - 1 + a//lcm(c, d) + 1
    y = b - b//c - 1 - b//d - 1 + b//lcm(c, d) + 1
    print(y-x)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

g = gcd(C, D)
l = (C*D)//g

x = B - ((B//C) + (B//D) - (B//l))
A = A-1
y = A - ((A//C) + (A//D) - (A//l))

print(x - y)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

if a % c == 0:
    c_div = (b//c) - (a//c) + 1
else:
    c_div = (b//c) - (a//c)
if a % d == 0:
    d_div = (b//d) - (a//d) + 1
else:
    d_div = (b//d) - (a//d)
if a % lcm == 0:
    cd_div = (b//lcm) - (a//lcm) + 1
else:
    cd_div = (b//lcm) - (a//lcm)

print(b-a+1 - (c_div + d_div - cd_div))

Submission status: Accepted

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

Submission status: Accepted

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

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())
fC = B // C - (A - 1) // C
fD = B // D - (A - 1) // D
l = lcm(C, D)
fCD = B // l - (A - 1) // l
print(B - A + 1 - (fC + fD - fCD))

Submission status: Accepted

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

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

P=[c,d,lcm(c,d)]
A=[]
for p in P:
    if a%p==0:
        left=a//p
    else:
        left=a//p+1
    right=b//p
    if left<=right:
        A.append(right-left+1)
    else:
        A.append(0)
print(b-a+1-A[0]-A[1]+A[2])

Submission status: Accepted

Solution code:
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  a, b, c, d = input_list()
  dc = b // c
  dd = b // d
  dcd = b // (lcm_base(c,d))
  bb = b - dc - dd + dcd
  
  ac = (a-1)//c
  ad = (a-1)//d
  acd = (a-1)//(lcm_base(c,d))
  aa = (a-1) - ac - ad + acd
  
  print(bb-aa)
  
import math
import fractions
import collections
import itertools
from functools import reduce
main()

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 calc_num(n, C, D):
    """
    0~Nまでで、C or Dで割り切れない数の個数
    """
    div_C = n//C
    div_D = n//D
    div_CD = n//(lcm(C, D))
    return n-div_C-div_D+div_CD


def solve():
    A, B, C, D = map(int, input().split())
    return calc_num(B, C, D)-calc_num(A-1, C, D)

print(solve())

Submission status: Accepted

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

num = (C*D)//(fractions.gcd(C, D))
if(A%C==0):
    num1 = A//C-1
else:
    num1 = A//C
if(A%D==0):
    num2 = A//D-1
else:
    num2 = A//D
if(A%num == 0):
    num3 = A//num-1
else:
    num3 = A//num
print(int(B-A+1-((B//C-num1)+(B//D-num2)-(B//num-num3))))

Submission status: Accepted

Solution code:
import math
import fractions

def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def countX(X) :
    if X > B :
        return 0
    minX = ceil(fractions.Fraction(A, X))
    maxX = floor(fractions.Fraction(B, X))

    return maxX - minX + 1

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

ans = B - A + 1

# 最小公倍数
Z = C * D // fractions.gcd(C,D)

ans -= countX(C)
ans -= countX(D)
ans += countX(Z)

print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D = (int(x) for x in input().split())
E = A-1
F = (C * D) // gcd(C,D)
nc = B // C
nc2 = E // C
nd = B // D
nd2 = E // D
ncd = int(B // F)
ncd2 = int(E // F)
print(B-A+1-nc+nc2-nd+nd2+ncd-ncd2)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

print(B-A-(B//C-(-(-A//C))+B//D-(-(-A//D))-(B//X-(-(-A//X)))))

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 count(n):
    c = n//C
    d = n//D
    g = gcd(C, D)
    l = C*D//g
    return n -c -d +n//l

print(count(B) - count(A-1))

Submission status: Accepted

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

ca = (A-1)//C 
cb = B//C

da = (A-1)//D
db = B//D

lcm = C * D //gcd(C,D)
cda = (A-1)//lcm
cdb = B//lcm

print(B-A+1-((cb-ca)+(db-da)-(cdb-cda)))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
from fractions import gcd
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

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

A, B, C, D = inp_list()

# (B 以下の条件を満たす自然数の個数) - (A - 1 以下の条件を満たす自然数の個数)
lcm_cd = lcm(C, D)
B_ans = B - B // C - B // D + B // lcm_cd
A1 = A - 1
A1_ans = A1 - A1 // C - A1 // D + A1 // lcm_cd
ans = B_ans - A1_ans
print(ans)

Submission status: Accepted

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

l = C * D //gcd(C, D)
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // l
y = B - B // C - B // D + B // l
print(y - x)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

def slice(n,c,d):
    ans=n
    ans-=(n//c)
    ans-=(n//d)
    ans+=(n//lcb(c,d))
    return ans

kai=slice(b,c,d)-slice(a-1,c,d)
print(kai)

Submission status: Accepted

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

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

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

max_num=lcb(c,d)
ans=(b-a+1)-((b//c)+(b//d)-(b//max_num))+(((a-1)//c)+((a-1)//d)-((a-1)//max_num))

print(ans)

Submission status: Accepted

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

l=C*D//fractions.gcd(C,D)
underB = B- (B//C+B//D-B//l)
underA = (A-1)- ((A-1)//C+(A-1)//D-(A-1)//l)
#print(underB, underA)
print(underB-underA)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
A,B,C,D = inputlist()
from fractions import gcd
def lcm(x,y):
    return (x*y)//gcd(x,y)
cd = lcm(C,D)
de = B-A+1
dec = (B//C)-((A-1)//C)
ded = (B//D)-((A-1)//D)
decd = (B//cd)-((A-1)//cd)
print(de-dec-ded+decd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

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

# 個数
#(b-a+1)

# aからbまでの間のcの倍数の個数
x = (b//c)-(a//c)
if a%c == 0:
    x += 1

# aからbまでの間のdの倍数の個数
y = (b//d)-(a//d)
if a%d == 0:
    y += 1

# aからbまでの間のaとbの公倍数の個数
z = (b//lcm(c,d))-(a//lcm(c,d))
if a%(c*d) == 0:
    z += 1

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

Submission status: Accepted

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

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

s = b - a + 1
cc = b // c - (a - 1) // c
dd = b // d - (a - 1) // d
cd = c * d // gcd(c, d)
cd = b // cd - (a - 1) // cd
s -= cc + dd - cd
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

import math

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

    
baisuu=lcm(C,D)

u_A=(A-1)-(A-1)//C-(A-1)//D+(A-1)//baisuu

u_B=B-B//C-B//D+B//baisuu

print(u_B-u_A)

Submission status: Accepted

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


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で割り切れる」数の総数を引く
s = B - A + 1
# print(s)

# Cで割り切れる数
c = B // C - (A - 1) // C

# Dで割りきれる数
d = B // D - (A - 1) // D

# CとDで割り切れる数
candd = B // lcm(C, D) - (A - 1) // lcm(C, D)

# CまたはDで割りきれる数
cord = c + d - candd

s -= cord
# print(s, c, d, candd, cord, s)
print(s)

Submission status: Accepted

Solution code:
import fractions

def ceil(n, m):
    if n % m == 0:
        ans = n // m
    else:
        ans = (n + m) // m
    return ans

q = [0] * 3
nmul = [0] * 3

lower, upper, q[0], q[1] = [int(x) for x in input().split()]
q[2] = (q[0] * q[1]) // fractions.gcd(q[0], q[1])

for i in range(3):
    left = lower if (lower % q[i] == 0) else lower + q[i] - (lower % q[i])
    nmul[i] = ceil( upper - left + 1, q[i])

ans = upper - lower + 1 - nmul[0] - nmul[1] + nmul[2]

print(ans)

Submission status: Accepted

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

c_count = b//c
d_count = b//d
# 最小公倍数で割る
c_d = b//(c*d//gcd(c, d))

print(b - c_count - d_count + c_d - (a-1 - (a-1)//c - (a-1)//d + (a-1)//(c*d//gcd(c, d))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import fractions

def solve(A: int, B: int, C: int, D: int):
    numCount = B - A + 1
    initialDivideC = A-A%C + C if A%C != 0 else A
    initialDivideD = A-A%D + D if A%D != 0 else A
    lcmCD = C*D//fractions.gcd(C,D)
    initialDivideLCM = A-A%lcmCD + lcmCD if A%lcmCD != 0 else A
    countC = (B - initialDivideC)//C + 1
    if initialDivideC > B:
        countC = 0
    countD = (B - initialDivideD)//D + 1
    if initialDivideD > B:
        countD = 0
    countLCM = (B - initialDivideLCM)//lcmCD + 1
    if initialDivideLCM > B:
        countLCM = 0
    print(numCount - countC - countD + countLCM)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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(a,b):
    return (a * b) // gcd(a, b)

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

E=lcm(C,D)

num_C=B//C-(A-1)//C
num_D=B//D-(A-1)//D
num_CD=B//E-(A-1)//E

ans=(B-A+1)-(num_C+num_D-num_CD)
print(ans)

Submission status: Accepted

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

def multiple(a, b):
    return a*b // euclid(a, b)

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

all = B - A + 1
x = B//C - (A-1)//C
y = B//D - (A-1)//D
lcm = multiple(C,D)
z = B//lcm - (A-1)//lcm

print(all - x - y + z)

Submission status: Accepted

Solution code:
# Euclidean Algorithm
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

# lcm (least common multiple)
def lcm(m, n):
    return m//gcd(m, n)*n

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

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

print(x - y - z + w)