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: Runtime Error

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

tot = b - a + 1
e = c*d//math.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: Runtime Error

Solution code:
import math

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

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

cd = lcm(c, d)

div_c = b // c - (a-1)//c
div_d = b // d - (a-1)//d
div_cd = b // cd - (a-1)//cd
count = b - a + 1 - div_c - div_d + div_cd
print(count)

Submission status: Runtime Error

Solution code:
import math
import os
import sys
from fractions import gcd
from decimal import *

from libs.debug import debug

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

A, B, C, D = list(map(int, sys.stdin.readline().split()))
A = Decimal(A)
B = Decimal(B)
C = Decimal(C)
D = Decimal(D)


def count(n):
    st = math.ceil(A / n)
    en = math.floor(B / n)
    return max(0, en - st + 1)


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

#
# N = int(sys.stdin.readline())
# A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

Submission status: Runtime Error

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

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)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from math import gcd

A, B, C, D = map(int, input().split())
G = gcd(C, D)
L = C * D // G
ca = (A - 1) // C
cb = B // C
da = (A - 1) // D
db = B // D
la = (A - 1) // L
lb = B // L
div = cb + db - (ca + da) - (lb - la)
print(B - (A - 1) - div)

Submission status: Runtime Error

Solution code:
import fractions

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

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

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

Submission status: Runtime Error

Solution code:
import sys
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]
from collections import defaultdict
import math

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

cd = int(c * d / math.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: Runtime Error

Solution code:
import math
a,b,c,d=list(map(int,input().split()))
a-=1
s=math.floor(b/c)-math.floor(a/c)
e=math.floor(b/d)-math.floor(a/d)
count=b-a-s-e
def lcm(x, y):
    return (x * y) // math.gcd(x, y)


com=lcm(c, d)
tmp=math.floor(b/com)-math.floor(a/com)
print(count+tmp)

Submission status: Runtime Error

Solution code:
#    !/usr/bin/env python3
#    encoding: UTF-8
#    Modified: <22/Jun/2019 05:50:52 PM>


#    ✪ H4WK3yE乡
#    Mohd. Farhan Tahir
#    Indian Institute Of Information Technology (IIIT), Gwalior


import sys
import os
from io import IOBase, BytesIO


def main():
    a, b, c, d = get_ints()
    l = 0
    if a % c == 0:
        l = a
    else:
        l = (a // c) * c + c
    r = (b // c) * c
    n1 = (r - l) // c + 1

    if a % d == 0:
        l = a
    else:
        l = (a // d) * d + d
    r = (b // d) * d
    n2 = (r - l) // d + 1

    from math import gcd
    g = (c * d) // gcd(c, d)
    if a % g == 0:
        l = a
    else:
        l = (a // g) * g + g
    r = (b // g) * g
    n3 = (r - l) // g + 1

    print(b - a + 1 - (n1 + n2 - n3))


BUFSIZE = 8192


class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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


class IOWrapper(IOBase):
    def __init__(self, file):
        py2 = round(0.5)
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2 == 1:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


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


def get_ints(): return map(int, sys.stdin.readline().split())


def input(): return sys.stdin.readline().strip()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
import math
A,B,C,D= map(int, input().split())
AC = (A-1)//C
AD = (A-1)//D
ACD =(A-1)//(C*D//math.gcd(C,D))
ans1 = A -1-AC -AD + ACD
BC = B//C
BD = B//D
BCD = B//(C*D//math.gcd(C,D))
ans2 = B - BC - BD +BCD
print(ans2-ans1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

num = np.arange(b - a + 1) + a
print(num[num % (c * d) != 0].shape[0])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
def lcm(a, b):
        return (a * b) // math.gcd(a, b)
def ca(a, b, c):
        return b // c - ((a - 1) // c)

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

Submission status: Runtime Error

Solution code:
from math import gcd

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

def kosu(b, c, d):
    return b - ((b // c) + (b // d) - (b // lcm(c, d)))

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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


def number(A,B,x):
    left = math.ceil(A/x)
    right = math.floor(B/x)
    return right - left + 1
    
    
    
    
ans = B-A+1
ans -=number(A,B,C)
ans -=number(A,B,D)
ans +=number(A,B,(C*D)//math.gcd(C,D))

print(ans)

Submission status: Runtime Error

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

p=c*d//(math.gcd(c,d))

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


print(y-x)

Submission status: Runtime Error

Solution code:
#!/usr/local/bin/python3

import math

def solve(a,b,c,d):
	a = a - 1
	l = int(c * d / math.gcd(c, d))
	r1 = a - (a // c + a // d - a // l)
	r2 = b - (b // c + b // d - b // l)
	return (r2 - r1)


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

Submission status: Runtime Error

Solution code:
import numpy as np

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

num = np.arange(b - a + 1) + a
print(num[np.logical_and(num % c != 0, num % d != 0)].shape[0])

Submission status: Runtime Error

Solution code:
import math

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

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

E = lcm(C,D)

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

Submission status: Runtime Error

Solution code:
import math

a,b,x,y = list(map(int, input().split()))

z = x * y // math.gcd(x,y)

def num(u,v,k):
    ww=v//k - (u-1)//k
    return ww

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

Submission status: Runtime Error

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

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]


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

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

Submission status: Runtime Error

Solution code:
from sys import stdin
import math

A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]


def div(n, x, y):
    lcs = int(x * y / math.gcd(x, y))
    return n - int(n // x) - int(n // y) + int(n // lcs)


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

Submission status: Runtime Error

Solution code:
import math

def main():
    a,b,c,d = map(int,input().split())
    total = b-a+1
    n1 = (b//c)-(a//c)
    n2 = (b//d)-(a//d)
    lcm = (c*d)//math.gcd(c,d)
    n3 = (b//lcm)-(a//lcm)
    if a%c == 0:
        n1 += 1
    if a%d == 0:
        n2 += 1
    if a%lcm == 0:
        n3 += 1

    #print(n1,n2,n3)
    print(total-n1-n2+n3)

main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

minc = math.ceil(a / c)
maxc = math.floor(b / c)
mind = math.ceil(a / d)
maxd = math.floor(b / d)

cd = c * d / math.gcd(c, d)
mincd = math.ceil(a / cd)
maxcd = math.floor(b / cd)

x = maxc - minc + 1
y = maxd - mind + 1
z = maxcd - mincd + 1

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

Submission status: Runtime Error

Solution code:
# coding=utf-8

A, B, C, D = 4, 9, 2, 3
A, B, C, D = 10, 40, 6, 8
A, B, C, D = 314159265358979323, 846264338327950288, 419716939, 937510582
A, B, C, D = map(int, raw_input().split())


def f(d):
    return B / d - (A - 1) / d


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

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

good = f(C) + f(D) - f(E)
print B - A + 1 - good

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:

import math
C,D,A,B =map(int,input().split())
la =[D//A,(C-1)//A]
lb =[D//B,(C-1)//B]
lcm = A*B //math.gcd(A,B)
lab =[D//lcm,(C-1)//lcm]

ans = la[0] +lb[0] -la[1] -lb[1] -(lab[0]-lab[1])
print(D-C+1-ans)

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
nc=b//c-(a-1)//c
nd=b//d-(a-1)//d
x=c*d//math.gcd(c,d)
ncd=b//x-(a-1)//x
#print(nc,nd,x,ncd)
print(b-a+1-nc-nd+ncd)

Submission status: Runtime Error

Solution code:
a, b, c, d = map(int, input().split())
l = lcm(c, d)
bad = (b // c) - ((a-1) // c) + (b // d) - ((a-1) // d) - (b // l) + ((a-1) // l)
ans = b - a + 1 - bad
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

x = c * d // math.gcd(c, d)

t1 = b // c
t2 = (a - 1) // c
u1 = b // d
u2 = (a - 1) // d
v1 = b // x
v2 = (a - 1) // x

ans = (b - a + 1) - (t1 - t2) - (u1 - u2) + (v1 - v2)
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

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

x = b//c - (a - 1)//c 

y = b//d - (a - 1)//d

cd = lcm(c, d)

z = b//cd - (a - 1)//cd

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

Submission status: Runtime Error

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

def solve(A: int, B: int, C: int, D: int):
    E = C * D // math.gcd(C, D)
    count_c = B // C - (A-1) // C
    count_d = B // D - (A-1) // D
    count_e = B // E - (A-1) // E
    print(B-A+1 - count_c - count_d + count_e)
    return


# Generated by 1.1.4 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: Runtime Error

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):
    return a if b == 0 else gcd(b, b%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: Runtime Error

Solution code:
from math 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: Runtime Error

Solution code:
from math 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: Runtime Error

Solution code:
import math

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/math.gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

Submission status: Runtime Error

Solution code:
import math
def LCM(a,b):
    return int(a*b/math.gcd(a,b))
A,B,C,D = map(int,input().split())#A以上B以下
L = LCM(C,D)
Cbaisu = B//C - A//C
Dbaisu = B//D - A//D
Lbaisu = B//L - A//L
print(B-A+1 - Cbaisu - Dbaisu + Lbaisu)

Submission status: Runtime Error

Solution code:
from math import gcd
g = lambda n, x: n // x
f = lambda l, r, x: g(r, x) - g(l - 1, x)
a, b, c, d = map(int, input().split())
res = b - a + 1
res -= f(a, b, c) + f(a, b, d) - f(a, b, c * d // gcd(c, d))
print(res)