Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03176 (python)

Fixed submission:
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    RMQ = SegmentTree([0] * N, merge_func=max, default=0)
    for i in range(N):
        maximum = RMQ.query(0, H[i]-1)
        RMQ.update(H[i]-1, maximum + A[i])
    print(RMQ.query(0, N))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [set() for _ in range(N)]
    for i in range(M):
        x, y = map(int, input().split())
        adj[x-1].add(y-1)
        adj[y-1].add(x-1)
    path = [-1] * N
    q = [(-(S-1), S-1)]
    while len(q):
        minimum, cur = heappop(q)
        minimum = -minimum
        if minimum <= path[cur]:
            continue
        path[cur] = minimum
        for a in adj[cur]:
            heappush(q, (-min(minimum, a), a))
    for i in range(N):
        if path[i] == i:
            print(i+1)


if __name__ == "__main__":
    main()
Problem p03177 (python)

Fixed submission:
import math
MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    x = int(math.log(K, 2))
    dp = [[[0] * N for _ in range(N)] for _ in range(x+1)]
    dp[0] = A
    for d in range(x):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[d+1][i][j] = (dp[d+1][i][j] +
                                     dp[d][i][k] * dp[d][k][j]) % MOD
    ans = [1] * N
    for d in range(x+1):
        if K & (2 ** d) == 0:
            continue
        prev = list(ans)
        ans = [0] * N
        for i in range(N):
            for j in range(N):
                ans[j] = (ans[j] + dp[d][i][j] * prev[i]) % MOD

    print(sum(ans) % MOD)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import math
MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    x = int(math.log2(K))
    dp = [[[0] * N for _ in range(N)] for _ in range(x+1)]
    dp[0] = A
    for d in range(x):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[d+1][i][j] = (dp[d+1][i][j] +
                                     dp[d][i][k] * dp[d][k][j]) % MOD
    ans = [1] * N
    for d in range(x+1):
        if K & (2 ** d) == 0:
            continue
        prev = list(ans)
        ans = [0] * N
        for i in range(N):
            for j in range(N):
                ans[j] = (ans[j] + dp[d][i][j] * prev[i]) % MOD

    print(sum(ans) % MOD)


if __name__ == "__main__":
    main()
Problem p03196 (python)

Fixed submission:
def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    if N >= 40:
        print(1)
        return

    i = 2
    retval = 1
    while P > 1 and i**N <= P:
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        retval *= i ** (cnt // N)
        i += 1
    print(retval)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    primes = []
    i = 2
    while i**N <= P:
        isprime = True
        for p in primes:
            if i % p == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
        i += 1

    F = {}
    i = 0
    while P > 1 and i < len(primes):
        factor = primes[i]
        while P % factor == 0:
            if factor not in F:
                F[factor] = 0
            F[factor] += 1
            P //= factor
        i += 1
    retval = 1
    for p in F:
        if F[p] >= N:
            retval *= p
    print(retval)


if __name__ == "__main__":
    main()
Problem p03230 (python)

Fixed submission:
import math


def main():
    N = int(input())
    x = math.floor(math.sqrt(N*2))
    if x * (x+1) != N*2:
        print("No")
        return
    print("Yes")
    print(x+1)
    s = [[] for _ in range(x+1)]
    counter = 1
    for i in range(x+1):
        for j in range(i+1, x+1):
            s[i].append(counter)
            s[j].append(counter)
            counter += 1
    for i in range(x+1):
        print(len(s[i]), *s[i])


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()
Problem p03294 (python)

Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(sum([x-1 for x in A]))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import math


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


def f(n, A):
    return sum([n % x for x in A])


def main():
    N = int(input())
    A = list(map(int, input().split()))
    retval = 1
    for a in A:
        retval = lcm(a, retval)
    print(f(retval - 1, A))


if __name__ == "__main__":
    main()
Problem p03409 (python)

Fixed submission:
def main():
    N = int(input())
    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "r"))
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "b"))
    points.sort(lambda x: x[0])
    singles = []
    retval = 0
    for p in points:
        x, y, c = p
        if c == "r":
            singles.append(y)
        if c == "b":
            maximum = (-1, -1)
            for i, v in enumerate(singles):
                if v < y and v > maximum[1]:
                    maximum = (i, v)
            if maximum[0] != -1:
                retval += 1
                singles.pop(maximum[0])
    print(retval)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "r"))
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "b"))
    points.sort(lambda x: x[0])
    singles = []
    retval = 0
    for p in points:
        x, y, c = p
        if c == "r":
            singles.append(y)
        if c == "b":
            maximum = (-1, -1)
            for i, v in enumerate(singles):
                if v < y and v > maximum[1]:
                    maximum = (i, v)
            if maximum[0] != -1:
                retval += 1
                singles.pop(maximum[0])
    print(retval)


if __name__ == "__main__":
    main()
Problem p03674 (python)

Fixed submission:
mod = int(1e9) + 7


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2)**2 % mod
    else:
        return power(x, y//2)**2 * x % mod


fact = [1] * int(1e5+2)
for i in range(1, int(1e5+2)):
    fact[i] = (i * fact[i-1]) % mod
inv = [1] * int(1e5+2)
inv[int(1e5+1)] = power(fact[int(1e5+1)], mod-2) % mod
for i in range(int(1e5), 0, -1):
    inv[i] = (inv[i+1] * (i+1)) % mod


def combination(n, r):
    return fact[n] * inv[r] * inv[n-r] % mod


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
mod = int(1e9) + 7


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2)**2 % mod
    else:
        return power(x, y//2)**2 * x % mod


fact = [1] * int(1e5+1)
for i in range(1, int(1e5+1)):
    fact[i] = (i * fact[i-1]) % mod
inv = [1] * int(1e5+1)
inv[int(1e5)] = power(fact[int(1e5)], mod-2) % mod
for i in range(int(1e5)-1, 0, -1):
    inv[i] = (inv[i+1] * (i+1)) % mod


def combination(n, r):
    return fact[n] * inv[r] * inv[n-r] % mod


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
mod = int(1e9) + 7


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2)**2 % mod
    else:
        return power(x, y//2)**2 * x % mod


def div(a, b):
    return a * power(b, mod-2) % mod


fact = [1] * int(1e5)
for i in range(1, int(1e5)):
    fact[i] = (i * fact[i-1]) % mod


def combination(n, r):
    return div(div(fact[n], fact[r]), fact[n-r])


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()
Problem p03746 (python)

Fixed submission:
from collections import deque


def remove(adj, a):
    for nxt in adj[a]:
        adj[nxt].remove(a)


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].add(b)
        adj[b].add(a)
    ans = deque([a, b])
    remove(adj, b)
    remove(adj, a)
    first = a
    last = b
    while len(adj[first]):
        nxt = list(adj[first])[0]
        ans.appendleft(nxt)
        remove(adj, nxt)
        first = nxt
    remove(adj, first)
    for a in ans:
        if a in adj[last]:
            adj[last].remove(a)
    while len(adj[last]):
        nxt = list(adj[last])[0]
        ans.append(nxt)
        remove(adj, nxt)
        last = nxt
    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import deque


def remove(adj, a):
    for nxt in adj[a]:
        adj[nxt].remove(a)


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].add(b)
        adj[b].add(a)
    ans = deque([a, b])
    remove(adj, a)
    remove(adj, b)
    first = a
    while len(adj[first]):
        nxt = list(adj[first])[0]
        ans.appendleft(nxt)
        remove(adj, nxt)
        first = nxt
    remove(adj, first)
    last = b
    for a in ans:
        if a in adj[last]:
            adj[last].remove(a)
    while len(adj[last]):
        nxt = list(adj[last])[0]
        ans.append(nxt)
        remove(adj, nxt)
        last = nxt
    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()
Problem p02641 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    X, N = MI()
    P = LI()

    ans = X
    if P == []:
        print(ans)
        return

    #
    # P = [i for i in range(1, 99)]
    # N = 100
    # X = 50

    mn = INF
    for i in range(X-110, X+110):
        # if i == X: continue
        if i not in P:
            if mn > abs(X - i):
                mn = abs(X - i)
                ans = i
            # print(i, abs(X - i), ans)
    print(ans)

if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def solve():
    N = II()
    A = LI()

    cost = {}
    for a in A:
        if cost.get(a, -1) == -1:
            cost[a] = 1
        else:
            cost[a] = 0

    A = sorted(A)

    memo = {}
    ans = 0
    for a in A:
        divs = make_divisors(a)
        for d in divs:
            if memo.get(d, -1) != -1:
                break
        else:
            ans += cost[a]
        memo[a] = 1
    print(ans)


if __name__ == '__main__':
    solve()
Problem p02691 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n = II()
    A = LI()

    memo = {}
    ans = 0
    for j in range(n):
        sa = j - A[j]
        ans += memo.get(sa, 0)
        wa = j + A[j]
        memo[wa] = memo.get(wa, 0) + 1
        # print(memo)
    print(ans)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n = II()
    A = LI()

    memo = {}
    ans = 0
    for j in range(n):
        sa = j - A[j]
        ans += memo.get(sa, 0)
        wa = j + A[j]
        memo[wa] = memo.get(wa, 0) + 1
        print(memo)
    print(ans)


if __name__ == '__main__':
    solve()
Problem p02761 (python)

Fixed submission:
n, m = map(int, input().split())
ans = [-1 for _ in range(n)]
end_flag = False
for _ in range(m):
    s, c = map(int, input().split())
    if ans[s-1] == -1:
        ans[s-1] = c
    elif ans[s-1] == c:
        continue
    else:
        end_flag = True
        break
# print(ans)
if ans[0] == 0 and n > 1:
    end_flag = True
if ans[0] == -1:
    if n > 1:
        ans[0] = 1
    else:
        ans[0] = 0

for i in range(1, n):
    if ans[i] == -1:
        ans[i] = 0
# print(ans)
if end_flag:
    print(-1)
else:
    ss = ''
    for i in ans:
        ss = ss + str(i)
    print(ss)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
ans = [-1 for _ in range(n)]
end_flag = False
for _ in range(m):
    s, c = map(int, input().split())
    if ans[s-1] == -1:
        ans[s-1] = c
    elif ans[s-1] == c:
        continue
    else:
        end_flag = True
        break
# print(ans)
if ans[0] == 0:
    end_flag = True
if ans[0] == -1:
    ans[0] = 1
if ans[1] == -1:
    ans[1] = 0
if ans[2] == -1:
    ans[2] = 0
# print(ans)
if end_flag:
    print(-1)
else:
    print('{}{}{}'.format(ans[0], ans[1], ans[2]))
Problem p02947 (python)

Fixed submission:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

from collections import Counter

def c2s(c):
    s = ''
    for key, val in c:
        # print(key, val)
        # s = f'{s}{key}{val}'
        s = '{}{}{}'.format(s, key, val)
    # print(s)
    return s

def choose2(n):
    if n == 1:
        return 0
    return n * (n - 1) // 2

def solve():
    n = II()
    S = [list(input()) for _ in range(n)]

    jisho = {}
    for s in S:
        c = sorted(Counter(s).items(), key=lambda x: x[0])
        # print(c)
        key = c2s(c)
        jisho[key] = jisho.setdefault(key, 0) + 1
    # print(jisho)
    ans = 0
    for val in jisho.values():
        ans = ans + choose2(val)

    print(ans)

if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

from collections import Counter

def c2s(c):
    s = ''
    for key, val in c:
        # print(key, val)
        s = f'{s}{key}{val}'
    # print(s)
    return s

def choose2(n):
    if n == 1:
        return 0
    return n * (n - 1) // 2

def solve():
    n = II()
    S = [list(input()) for _ in range(n)]

    jisho = {}
    for s in S:
        c = sorted(Counter(s).items(), key=lambda x: x[0])
        # print(c)
        key = c2s(c)
        jisho[key] = jisho.setdefault(key, 0) + 1
    # print(jisho)
    ans = 0
    for val in jisho.values():
        ans = ans + choose2(val)

    print(ans)

if __name__ == '__main__':
    solve()
Problem p02995 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')

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

def f(x, c, d):
    r = x
    r -= x // c
    r -= x // d
    r += x // lcm(c, d)
    return r

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

def solve():
    a, b, c, d = MI()

    # g = lcm(c, d)
    # bb = b - (b // c) - (b // d) + (b // g)
    # a = a - 1
    # aa = a - (a // c) - (a // d) + (a // g)
    # print(bb - aa)
    print(f(b, c, d) - f(a-1, c, d))
    # print(f2(b, c, d) - f2(a-1, c, d))


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

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

from math import ceilf
from fractions import gcd

def solve():
    a, b, c, d = MI()

    e = b // c
    f = ceil(a / c)
    c2 = e - f + 1
    g = b // d
    h = ceil(a / d)
    d2 = g - h + 1

    cd = lcm(c, d)
    cdr = b // cd
    cdl = ceil(a / cd)
    cd2 = cdr - cdl + 1
    # print(c2, d2, cd2)
    print(b - a + 1 - c2 - d2 + cd2)


if __name__ == '__main__':
    solve()