Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def comb(n, k, p):
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n - k) % p
    return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p


def power_func(a, b, p):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

X, Y = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)


Fixed submission:
def comb(n, k, mod):
    if k > (n // 2):
        k = n - k
    a = 1
    for i in range(k):
        a *= (n - i)
        a %= mod
    for i in range(k - 1):
        a = (a * pow(k - i, mod - 2, mod)) % mod

    return a

X, Y = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def check(n, k , a, f, x):
    training_cnt = 0
    for i in range(n):
        t = x // f[i]  #a[i]をこれ以下にしたい。
        d = a[i] - t
        if d > 0:
            training_cnt += d
        if training_cnt > k:
            return False
    else:
        return True

def main():
    N, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    F = sorted([int(i) for i in input().split()], reverse=True)

    if check(N, K, A, F, 0):
        print(0)
        return


    left = 0
    right = 10 ** 12

    while left + 1 < right:
        mid = (left + right) // 2
        if check(N, K, A, F, mid):
            right = mid
        else:
            left = mid

    print(right)

if __name__ == '__main__':
    main()




Fixed submission:
def check(n, k , a, f, x):
    training_cnt = 0
    for i in range(n):
        t = x // f[i]  #a[i]をこれ以下にしたい。
        d = a[i] - t
        if d > 0:
            training_cnt += d
        if training_cnt > k:
            return False
    else:
        return True

def main():
    N, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    F = sorted([int(i) for i in input().split()], reverse=True)

    if check(N, K, A, F, 0):
        print(0)
        return


    left = 0
    right = 10 ** 12

    while left + 1 < right:
        mid = (left + right) // 2
        if check(N, K, A, F, mid):
            right = mid
        else:
            left = mid

    print(right)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    s = input()
    if s[0] == 'S':
        print('Cloudy')
    elif s[0] == 'C':
        print('Rainy')
    else:
        print('Sunny)

if __name__ == '__main__':
    main()


Fixed submission:
def main():
    s = input()
    if s[0] == 'S':
        print('Cloudy')
    elif s[0] == 'C':
        print('Rainy')
    else:
        print('Sunny')

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import  heapq

N, M = map(int, input().split())
data = [[int(x) for x in input().split()] for i in range(N)]

data.sort(reverse=True, key=lambda x: (-x[0], x[1]))

day = M
reward = 0

# d日前
q = []
i = 0
for d in range(1, M + 1):
    for t in range(i, N):
        if data[t][0] > d:
            break
        i += 1
        heapq.heappush(q, -1 * data[t][1])
    reward += heapq.heappop(q)

print(-1 * reward)





Fixed submission:
import  heapq
 
N, M = map(int, input().split())
data = [[int(x) for x in input().split()] for i in range(N)]
data.sort(reverse=True, key=lambda x: (-x[0], x[1]))
 
day = M
reward = 0
 
# d日前
q = []
i = 0
for d in range(1, M + 1):
    for t in range(i, N):
        if data[t][0] > d:
            break
        i += 1
        heapq.heappush(q, -1 * data[t][1])
    if q:
        reward += heapq.heappop(q)
 
print(-1 * reward)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ai = list(map(int, input().split()))

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    s = [ai[x] == 1 for x in range(i + 1, N) if (x + 1) % (i + 1) == 0]
    cnt = s.count(True)
    if cnt & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1

print(box.count(1))
for x in box:
    if x == 1:
        print(x)


Fixed submission:
N = int(input())
ai = list(map(int, input().split()))

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    value = i + 1
    sum = 0
    for j in range(value * 2 - 1, N, value):
        sum += box[j]
    if sum & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1
print(box.count(1))
for i in range(N):
    if box[i] == 1:
        print(i + 1)
Buggy python submission (verdict: Runtime Error):
def comb(a, b, mod):
    if a // 2 < b:
        b = a - b
    t = 1
    for i in range(b):
        t *= (a - i) % mod
    s = 1
    for i in range(1, b + 1):
        s *= i % mod
    return (t // s) % mod



N, K = map(int, input().split())
r = N - K
mod = 1000000007

if K > N // 2:
    

for i in range(1, K + 1):
    print(comb(r + 1, i, mod) * comb(K - 1, i - 1, mod) % mod)
    
    




Fixed submission:
def comb(a, b, mod):
    if a < b :
        return 0
    if (a // 2) < b:
        x = a - b
        # print(f'{b}　→ {x}')
        b = x
    t = 1
    for i in range(b):
        t *= (a - i) % mod
    s = 1
    for i in range(1, b + 1):
        s *= i % mod
    return (t // s) % mod

N, K = map(int, input().split())
r = N - K
mod = 1000000007

for i in range(1, K + 1):
        first = comb(r + 1, i, mod)
        if first == 0:
            second = 0
        else:
            second = comb(K - 1, i - 1, mod)
        print(first * second % mod)

Buggy python submission (verdict: Time Limit Exceeded):
def comb(a, b, mod):
    t = 1
    for i in range(b):
        t *= (a - i) % mod
    s = 1
    for i in range(1, b + 1):
        s *= i % mod
    return (t // s) % mod



N, K = map(int, input().split())
r = N - K
mod = 1000000007
for i in range(1, K + 1):
    print(comb(r + 1, i, mod) * comb(K - 1, i - 1, mod) % mod)




Fixed submission:
def comb(a, b, mod):
    if a < b :
        return 0
    if (a // 2) < b:
        x = a - b
        # print(f'{b}　→ {x}')
        b = x
    t = 1
    for i in range(b):
        t *= (a - i) % mod
    s = 1
    for i in range(1, b + 1):
        s *= i % mod
    return (t // s) % mod

N, K = map(int, input().split())
r = N - K
mod = 1000000007

for i in range(1, K + 1):
        first = comb(r + 1, i, mod)
        if first == 0:
            second = 0
        else:
            second = comb(K - 1, i - 1, mod)
        print(first * second % mod)
Buggy python submission (verdict: Runtime Error):
N, A = map(int, input().split())
print(0 if X < A else 10)

Fixed submission:
X, A = map(int, input().split())
print(0 if X < A else 10)
Buggy python submission (verdict: Runtime Error):
    a, b, c = map(int, input().split())
    print(a + b + c - max(a, b, c))

Fixed submission:
a, b, c = map(int, input().split())
print(a + b + c - max(a, b, c))

Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input().split())
print(a + b + c - , max(a, b, c))

Fixed submission:
a, b, c = map(int, input().split())
print(a + b + c - max(a, b, c))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
V = [int(i) for i in input().split()]

ans = -1
for i in range(K + 1): #i個ゲット
    for l in range(i + 1): #左からいくつのindexまでとるか
        a = V[0:l] + V[N - (i - l):N]
        a.sort()

        # K- i 個負のvalueを捨てれる
        t = 0
        s = sum(a)
        while i > t and K - i > t:
            if a[t] >= 0:
                break
            s -= a[t] #負の減算なので加算
            t += 1
        ans = max(ans, s)

print(ans)


Fixed submission:
N, K = map(int, input().split())
V = [int(i) for i in input().split()]

ans = -1
for i in range(min(N + 1, K + 1)): #i個ゲット
    for l in range(i + 1): #左からいくつのindexまでとるか
        a = V[0:l] + V[N - (i - l):N]
        a.sort()

        # K- i 個負のvalueを捨てれる
        t = 0
        s = sum(a)
        while i > t and K - i > t:
            if a[t] >= 0:
                break
            s -= a[t] #負の減算なので加算
            t += 1
        ans = max(ans, s)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
N, K = map(int, input().split())

M = []
x = 1
while x < (10 ** 5) * 2:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
ans = p / N + p1
print('{0:.10f}'.format(ans))






#*1/N


Fixed submission:
import math
N, K = map(int, input().split())

M = []
x = 1
while x < (10 ** 5) * 2:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
ans = p / N + p1
print('{0:.10f}'.format(ans))

Buggy python submission (verdict: Runtime Error):
import math
N, K = map(int, input().split())

M = []
x = 1
while x < (10 ** 5) * 2:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
print(p / N + p1)


Fixed submission:
import math
N, K = map(int, input().split())

M = []
x = 1
while x < (10 ** 5) * 2:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
ans = p / N + p1
print('{0:.10f}'.format(ans))

Buggy python submission (verdict: Runtime Error):
import math
N, K = map(int, input().split())

M = []
x = 1
while x < 10 ** 5:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
print(p / N + p1)


Fixed submission:
import math
N, K = map(int, input().split())

M = []
x = 1
while x < (10 ** 5) * 2:
    M.append(1 / x)
    x <<= 1

p1 = max((N - K + 1) / N, 0)
p = 0
for i in range(1, min(N + 1, K)):
    t = int(math.log2(K / i)) + 1
    if K % i == 0 and  (K // i) & (K // i - 1) == 0:
        t -= 1
    p += M[t]
ans = p / N + p1
print('{0:.10f}'.format(ans))
Buggy python submission (verdict: Runtime Error):
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, c):
        if self.par[c] == c:
            return c

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
        else:
            self.par[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

N, M = map(int, input().split())
uf = union_find(N)

for i in range(M):
    x, y, z = map(int, input().split())
    uf.union(x, y)


print([i == v for i, v in enumerate(uf.par[])].count(True)) - 1






Fixed submission:
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, c):
        if self.par[c] == c:
            return c

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
        else:
            self.par[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

N, M = map(int, input().split())
uf = union_find(N)

for i in range(M):
    x, y, z = map(int, input().split())
    uf.union(x, y)


print([i == v for i, v in enumerate(uf.par)].count(True) - 1)
Buggy python submission (verdict: Time Limit Exceeded):
def gca(x, y):
    if x == 0:
        return y
    return gca(y % x, x)

N = int(input())
A = [int(i) for i in input().split()]

dic = {}



maxg = 0
for ignore in  range(N):
    g = A[0]
    if ignore == 0:
        g = A[1]
    for i in range(N):
        if i == ignore:
            continue
        x = g
        y = A[i]
        if y > x : x, y = y, x
        if (x, y) in dic:
            g = dic[(x, y)]
        else:
            g = gca(g, A[i])
        dic[(x, y)] = g

    maxg = max(g, maxg)

print(maxg)

Fixed submission:
def gca(x, y):
    if x == 0:
        return y
    return gca(y % x, x)

N = int(input())
A = [int(i) for i in input().split()]

L = [0] * N
R = [0] * N
L[0] = A[0]
R[N - 1] = A[N - 1]

for i in range(1, N):
    L[i] = gca(A[i], L[i - 1])
for i in range(N - 2, -1, -1):
    R[i] = gca(A[i], R[i + 1])
maxg = 0
for i in range(1, N - 1):
    maxg = max(maxg, gca(L[i - 1], R[i + 1]))

print(max(L[N - 2], R[1], maxg))

Buggy python submission (verdict: Time Limit Exceeded):
def gca(x, y):
    if x == 0:
        return y
    return gca(y % x, x)

N = int(input())
A = [int(i) for i in input().split()]

maxg = 0
for ignore in  range(N):
    g = A[0]
    if ignore == 0:
        g = A[1]
    for i in range(N):
        if i == ignore:
            continue
        g = gca(g, A[i])

    maxg = max(g, maxg)

print(maxg)

Fixed submission:
def gca(x, y):
    if x == 0:
        return y
    return gca(y % x, x)

N = int(input())
A = [int(i) for i in input().split()]

L = [0] * N
R = [0] * N
L[0] = A[0]
R[N - 1] = A[N - 1]

for i in range(1, N):
    L[i] = gca(A[i], L[i - 1])
for i in range(N - 2, -1, -1):
    R[i] = gca(A[i], R[i + 1])
maxg = 0
for i in range(1, N - 1):
    maxg = max(maxg, gca(L[i - 1], R[i + 1]))

print(max(L[N - 2], R[1], maxg))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = 0
while True:
    if '01' in S:
        i = S.index('01')
        S = S[0 : i] + S[i + 2:]
    elif '10' in S:
        i = S.index('10')
        S = S[0 : i] + S[i + 2:]
    else:
        break
    n += 1

print(2 * n)




Fixed submission:
S = input()
A = [int(c) for c in S]

l = len(S)
L = [[0 for j in range(l + 1)] for i in range(2)]
R = [[0 for j in range(l + 1)] for i in range(2)]

for i in range(l):
    L[0][i + 1] = L[0][i]
    L[1][i + 1] = L[1][i]
    L[A[i]][i + 1] += 1

for i in range(l - 1, -1, -1):
    R[0][i] = R[0][i + 1]
    R[1][i] = R[1][i + 1]
    R[A[i]][i] += 1

k = 0
for a, b, c, d in zip(L[0], R[1], L[1], R[0]):
    k = max(k, min(a, b) + min(c, d))

print(k * 2)
Buggy python submission (verdict: Runtime Error):
#
# joi2008yo e
#
import sys
from io import StringIO
import unittest
import copy


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 5
0 1 0 1 0
1 0 0 0 1"""
        output = """9"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1"""
        output = """15"""
        self.assertIO(input, output)


def resolve():
    R, C = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(R)]
    A_rev = [[1 - v for v in a] for a in A]

    ans = 0
    for bit in range(1 << R):
        num = 0
        T = copy.deepcopy(A)
        for i, t in enumerate(T):
            if 1 << i & bit:
                T[i] = A_rev[i]

        T = list(zip(*T))
        for t in T:
            num += max(t.count(0), t.count(1))
        ans = max(ans, num)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Fixed submission:
#
# abc147 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    ans = 0
    for bit in range(1 << N):
        t = 0
        for i in range(N):
            if bit & (1 << i):
                for c in C[i]:
                    if bit & (1 << c[0]-1) != (1 << c[0]-1)*c[1]:
                        break
                else:
                    t += 1
        if t == bin(bit).count("1"):
            ans = max(ans, t)
    print(ans)


if __name__ == "__main__":
     # unittest.main()
     resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from io import StringIO
import unittest


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


def resolve():
    N = int(input())
    S = input()

    R = S[0]
    for i in range(1, N):
        if S[i] != R[-1]:
            R += S[i]
    print(len(R))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """10
aabbbbaaca"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
aaaaa"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """20
xxzaffeeeeddfkkkkllq"""
        output = """10"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()


Fixed submission:
import sys
from io import StringIO
import unittest


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


def resolve():
    N = int(input())
    S = input()

    R = S[0]
    for i in range(1, N):
        if S[i] != R[-1]:
            R += S[i]
    print(len(R))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """10
aabbbbaaca"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
aaaaa"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """20
xxzaffeeeeddfkkkkllq"""
        output = """10"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()
Buggy python submission (verdict: Runtime Error):
def main():
    L, R = map(int, input().split())

    ans = L * R % 2019
    if R - L >= 2019
        ans = 0
    else:
        l = L % 2019
        r = R % 2019
        if l == r:
            ans = 2*l
        else:
            ans = min(l*(l+1), l*r)

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    L, R = map(int, input().split())

    ans = L * R % 2019
    if R - L >= 2019:
        ans = 0
    else:
        for i in range(L, R+1):
            for j in range(i+1, R+1):
                ans = min(ans, i*j % 2019)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    S = input()
    if S[0] == S[1] and S[2] == S[3]:
        ans = "Yes"
    elif S[0] == S[2] and S[1] == S[3]:
        ans = "Yes"
    elif S[0] == S[3] and S[1] == S[2]:
        ans = "Yes"
    else:
    else:
        ans = "No"
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    S = input()
    if S[0] == S[1] == S[2] == S[3]:
        ans = "No"
    elif S[0] == S[1] and S[2] == S[3]:
        ans = "Yes"
    elif S[0] == S[2] and S[1] == S[3]:
        ans = "Yes"
    elif S[0] == S[3] and S[1] == S[2]:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


def main():
    A, B, C, D = map(int, input().split())
    tmp = 0
    R = int(C * D / gcd(C, D))
    flag = True
    i = 1
    while flag:
        if C * i < A:
            i += 1
        elif C * i <= B:
            i += 1
            tmp += 1
        else:
            break

    flag = True
    i = 1
    while flag:
        if D * i < A:
            i += 1
        elif D * i <= B:
            i += 1
            tmp += 1
        else:
            break

    flag = True
    i = 1
    while flag:
        if R * i < A:
            i += 1
        elif R * i <= B:
            i += 1
            tmp -= 1
        else:
            break

    print(B-A+1-tmp)


if __name__ == '__main__':
    main()

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


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

    tmp = B // C - (A-1) // C + B // D - (A-1) // D - B // R + (A-1) // R
    print(B-A+1-tmp)


if __name__ == '__main__':
    main()