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:
def euclid(a,b):
	c=0
	if (a-b)<0:
		c=a
		a=b
		b=c
	r=-1
	while r!=0:
		r=a%b
		a=b
		b=r
	return a

A,B,C,D=map(int,input().split())
c1=(A-1)//C
d1=(A-1)//D
c2=B//C
d2=B//D
k=euclid(C,D)
CD=C*D//k
cd1=(A-1)//CD
cd2=B//CD
c3=c2-c1
d3=d2-d1
cd3=cd2-cd1
print(B-A+1-c3-d3+cd3)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

def gcd(x,y):  #最大公約数
    if x==0:
        return y
    else:
        return gcd(y%x,x)

a,b,c,d=intinput()
sums=b-a+1
c1=(a-1)//c
c2=b//c
d1=(a-1)//d
d2=b//d
lcmcd=(c*d)//gcd(c,d)
cd1=(a-1)//lcmcd
cd2=b//lcmcd
print(sums-(c2+d2-cd2-(c1+d1-cd1)))

Submission status: Accepted

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

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

import fractions

two = B // C
three = B //D

g = int(lcd(C,D))
six = B // (g)

btwo = (A-1) // C
bthree = (A-1) //D
bsix = (A-1) // (g)

a = B - two - three  + six
b = (A-1) - btwo - bthree  + bsix



print(a - b)

Submission status: Accepted

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

def notdiv(x,c,d):
    e=c*d//gcd(c,d)
    return x-((x//c)+(x//d)-(x//e))

print(notdiv(b,c,d)-notdiv(a-1,c,d))

Submission status: Accepted

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

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

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

Submission status: Accepted

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


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


def div_num(n: int, a: int)->int:
    '''n 以下の整数で a で割り切れるものの数を計算します。
    '''
    return n // a


def anti_division(A: int, B: int, C: int, D: int)->int:
    A -= 1

    n1 = div_num(A, C)+div_num(A, D)-div_num(A, lcm(C, D))
    n2 = div_num(B, C)+div_num(B, D)-div_num(B, lcm(C, D))

    return (B-A) - (n2-n1)


if __name__ == "__main__":
    A, B, C, D = map(int, input().split())

    ans = anti_division(A, B, C, D)
    print(ans)

Submission status: Accepted

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

import os
import sys
from io import BytesIO, IOBase

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


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


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


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

    cm = lcm(c, d)

    dc = (b // c) - (a // c)
    dd = (b // d) - (a // d)
    dcd = (b // cm) - (a // cm)

    print((b - a) - ((dc + dd) - dcd))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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


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

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
A, B, C, D=map(int, input().split())
def func(c):
    global A, B
    return B//c-(A-1)//c

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
gcd = gcd(C,D)
A=A-1
A_C = A//C
A_D = A//D
A_CD = A//int(C*D/gcd)

B_C = B//C
B_D = B//D
B_CD = B//int(C*D/gcd)

ans = B-A-(B_C-A_C)-(B_D-A_D)+(B_CD-A_CD)
print(ans)

Submission status: Accepted

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

lcm = C * D //fractions.gcd(C, D)
b =  B // C + B // D - B // lcm
b = B - b

A -= 1
a =  A // C + A // D - A // lcm
a = A - a

print(b - a)

Submission status: Accepted

Solution code:


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


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

def lcm(x, y):
    return (x * y) // 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: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd
a, b, c, d = map(int, input().split())
l = c * d // gcd(c, d)
a -= 1
nac = a // c
nad = a // d
nal = a // l
nbc = b // c
nbd = b // d
nbl = b // l
na = nac + nad - nal
nb = nbc + nbd - nbl
print(b - a - (nb - na))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd 

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

def countnumber(x):
    number = B // x
    number -= A // x
    if A % x == 0:
        number += 1
    return number 

number = countnumber(C) + countnumber(D) - countnumber(LCM)
answer = B - A - number + 1
print(answer)

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())
E = lcm(C,D)
i = (A-1)//C
j = B//C
k = (A-1)//D
l = B//D

m = (A-1)//E
n = B//E

ans = B - A + 1 - ((j-i) + (l-k) - (n-m))

print(ans)

Submission status: Accepted

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

def kosuu(a, b, hoge):
    mae = a // hoge
    if a%hoge == 0:
        mae -= 1
    ato = b // hoge
    wareru = ato - mae
    return wareru

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

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

c_kosuu = kosuu(A,B,C)
d_kosuu = kosuu(A,B,D)
cd_kosuu = kosuu(A,B,lcm(C,D))

# cd_kosuu

print(B-A+1-(c_kosuu+d_kosuu-cd_kosuu))

Submission status: Accepted

Solution code:
import fractions
import math
a,b,c,d=map(int,input().split())
k=c*d//fractions.gcd(c,d)
ans=b-a+1
ca=(a-1)//c+1
cb=b//c
da=(a-1)//d+1
db=b//d
ka=(a-1)//k+1
kb=b//k
ans-=cb-ca+1
ans-=db-da+1
ans+=kb-ka+1
print(ans)

Submission status: Accepted

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

# a以上の最小のbの倍数
def overMinMulti(a, b):
  if a % b == 0:
    return a
  return (a // b + 1) * b

# a以下の最大のbの倍数
def underMaxMulti(a, b):
  return a // b * b

A, B, C, D = map(int, input().split())
E = C * D // gcd(C, D)
print(
  B - A + 1
  - ((underMaxMulti(B, C) - overMinMulti(A, C)) // C + 1)
  - ((underMaxMulti(B, D) - overMinMulti(A, D)) // D + 1)
  + ((underMaxMulti(B, E) - overMinMulti(A, E)) // E + 1)
)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(x,y):
    return (x*y)//gcd(x,y)
    
a,b,c,d=map(int,input().split())

dd=(b//d)-((a-1)//d)
cc=(b//c)-((a-1)//c)
cd=(b//lcm(c,d))-((a-1)//lcm(c,d))


print(b-a+1-cc-dd+cd)

Submission status: Accepted

Solution code:
from fractions import gcd

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

A, B, C, D = [int(i) for i in input().split()]

c = (B // C) - ((A - 1) // C)
d = (B // D) - ((A - 1) // D)
cd = (B // (lcm(C, D))) - (A - 1) // (lcm(C, D))

N = B - A + 1

print(N - c - d + cd)

Submission status: Accepted

Solution code:

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



C,D,A,B =map(int,input().split())
la =[D//A,(C-1)//A]
lb =[D//B,(C-1)//B]
lcm = A*B //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: Accepted

Solution code:
def gcd(x,y):
    while y:
        x,y=y,x%y
    return x

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: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
e=lcm(c,d)
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
ee=b//e-(a-1)//e
print(b-a+1-cc-dd+ee)

Submission status: Accepted

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

def euclid(p, q):
    if p > q:
        p, q = q, p
    while q > 0:
        p, q = q, p % q
    return p

def lcm(p, q):
    return p * q // euclid(p, q)

c_a = (a-1) // c
c_b = b // c
d_a = (a-1) // d
d_b = b // d
cd_a = (a-1) // lcm(c, d)
cd_b = b // lcm(c, d)
# print(c_a, c_b, d_a, d_b, cd_a, cd_b)

print(b - a + 1 - ((c_b + d_b - cd_b) - (c_a + d_a - cd_a)))

Submission status: Accepted

Solution code:
import fractions

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

def anti_division(n,a,b):
    anti_a = n // a
    anti_b = n // b
    anti_ab = n // lcm(a,b)
    return n - anti_a - anti_b + anti_ab


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

Submission status: Accepted

Solution code:
class LCM():
    #a、bに最小公倍数または最大公約数を求めたい二つの整数の組を入れる
    def __init__(self,a,b):
        if a < b:a,b = b,a
        self.a = a
        self.b = b

    #最大公約数
    def gcd(self):
        a,b = self.a,self.b
        def nono(a,b):
            if a < b:a,b = b,a
            if a % b == 0:return b
            else:return nono(b,a % b)
        return nono(a,b)

    #最小公倍数
    def lcm(self):
        a,b = self.a,self.b
        def nono(a,b):
            if a < b:a,b = b,a
            if a % b == 0:return b
            else:return nono(b,a % b)
        num = nono(a,b)
        return a*b//num
a,b,c,d = map(int,input().split())
a -= 1
#a
numa = 0
numa += a // c
numa += a // d
cc = LCM(c,d).lcm()
numa -= a // cc

numb = 0
numb += b // c
numb += b // d
numb -= b // cc
print((b-a) - (numb - numa))

Submission status: Accepted

Solution code:
from fractions import gcd

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

a = A // C + A // D - A // ((C * D) // gcd(C, D))
b = B // C + B // D - B // ((C * D) // gcd(C, D))

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

Submission status: Accepted

Solution code:
import fractions

a, b, c, d = map(int, input().split())
num = b - a + 1
div_c = b // c - (a - 1) // c 
div_d = b // d - (a - 1) // d 
lcm_cd = c * d // fractions.gcd(c, d)
div_lcm = b // lcm_cd - (a - 1) // lcm_cd
print(num - div_c -div_d + div_lcm)

Submission status: Accepted

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

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: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
A,B,C,D= map(int, input().split())
AC = (A-1)//C
AD = (A-1)//D
ACD =(A-1)//(C*D//gcd(C,D))
ans1 = A -1-AC -AD + ACD
BC = B//C
BD = B//D
BCD = B//(C*D//gcd(C,D))
ans2 = B - BC - BD +BCD
print(ans2-ans1)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

import fractions
A, B, C, D = mi()

cdall = B//round((C * D / fractions.gcd(C, D)))#1～BにおけるC*Dの約数の個数
call = B//C
dall = B//D

cdminus = (A-1)//round((C * D / fractions.gcd(C, D)))
cminus = (A-1)//(C)
dminus = (A-1)//(D)

divcntall = call+dall-cdall
divcntminus = cminus+dminus-cdminus

print(B-(A-1)-(divcntall-divcntminus))

Submission status: Accepted

Solution code:
#    !/usr/bin/env python3
#    encoding: UTF-8
#    Modified: <22/Jun/2019 05:52:43 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 fractions 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: Accepted

Solution code:
def gcd(n1,n2):
    if n2 > n1:
        return gcd(n2,n1)
    if n2 == 0:
        return n1
    return gcd(n2,n1%n2)

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)//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: 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 solve(warareru, c, d):
    #cで割れる数.
    num1 = (warareru) // c
    #dで割れる数
    num2 = (warareru) // d
    #cとdで割れる数
    waru = lcm(c, d)
    num3 = (warareru) // waru
    return warareru - num1 - num2 + num3
    
a, b, c, d = map(int, input().split())

ans1 = solve(a-1, c, d)
ans2 = solve(b, c, d)
print(ans2-ans1)

Submission status: Accepted

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

cmul = (B // C) - ((A - 1) // C)
dmul = (B // D) - ((A - 1) // D)
CD = C * D // gcd(C, D)
cdmul = (B // CD) - ((A - 1) // CD)

print((B - A + 1) - (cmul + dmul - cdmul))

Submission status: Accepted

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

A, B, C, D = list(map(int, input().split()))
_all = B - A + 1
lcm = int(C * D / 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: Accepted

Solution code:
from fractions 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: Accepted

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

import fractions

def solve(a,b,c,d):
	a = a - 1
	l = c * d // fractions.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: 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 func(n,c,d):
    a1 = n//c
    a2 = n//d
    a3 = n//lcm(c,d)
    return n - (a1+a2-a3)

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
A, B, C, D = map(int, input().split())
E = C * D // gcd(C, D)
x = A - 1 - (A - 1) // C - (A - 1) // D + (A - 1) // E
y = B - B // C - B // D + B // E
print(y - x)

Submission status: Accepted

Solution code:

def divides_u(x,y):
    return x // y
def divides_d(x,y):
    return (x+y-1) // y
def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcd(a,b):
	return a * b // gcd(a,b)


a, b, c, d =  [ int(v) for v in input().split() ]
e = lcd(c,d)
n = b - a + 1

m1 = divides_u(b,c) - divides_d(a,c) + 1
m2 = divides_u(b,d) - divides_d(a,d) + 1
m3 = divides_u(b,e) - divides_d(a,e) + 1


print(n-m1-m2+m3)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

# a, bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

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

# print(lcm(C, D))
A, B, C, D = l_inpl()
A -= 1
B_ans = B - (B // C + B // D - B // lcm(C, D))
# print(B_ans)
A_ans = A - (A // C + A // D - A // lcm(C, D))
# print(A_ans)
print(B_ans - A_ans)

Submission status: Accepted

Solution code:
A,B,C,D = [int(i) for i in input().split()]

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

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

E = lcm(C,D)

p = B-A+1

ac = p//C
if A%C+p%C >= C+1:
    ac += 1

ad = p//D
if A%D+p%D >= D+1:
    ad += 1

ae = p//E
if A%E+p%E >= E+1:
    ae += 1

print(p-(ac+ad-ae))

Submission status: Accepted

Solution code:
def get_a(a, b, c):
	q1, mod1 = divmod(a, c)
	q2, mod2 = divmod(b, c)
	if mod1 == 0:
		count = q2 - q1 + 1
	else:
		count = q2 - q1
	return count

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

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

def main():
	import sys
	input = sys.stdin.readline
	A, B, C, D = map(int, input().split())
	LCM = lcm(C, D)
	notans = get_a(A, B, C) + get_a(A, B, D) - get_a(A, B, LCM)
	sum = B - A + 1
	print(sum - notans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

zero_b = b - b // c - b // d + b // lcm(c,d)
zero_a = (a-1) - (a-1) // c - (a-1) // d + (a-1) // lcm(c,d)

print(zero_b - zero_a)

Submission status: Accepted

Solution code:
import fractions

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

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

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

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
p=c*d//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: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

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

#B
def B():
    n, l = LI()
    lis = [l + i for i in range(n)]
    s = sum(lis)
    a = inf
    for i in lis:
        if abs(a) > abs(i):
            a = i
    print(s-a)
    return

#C
def C():
    def gcd(a, b):
        a, b = max(a, b), min(a, b)
        while b:
            a, b = b, a % b
        return a
    def lcm(a, b):
        return a * b // gcd(a, b)
    a, b, c, d = LI()
    x = b // c - (a-1) // c
    y = b // d - (a-1) // d
    z = b // lcm(c , d) - (a-1) // lcm(c , d)
    print(b-a+1-(x+y-z))
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
a,b,c,d = map(int, input().split())

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

x = c*d//gcd(c,d)
a -= 1
ans = b//c - a//c
ans += b//d - a//d
ans -= b//x - a//x

ans = b-a-ans
print(ans)

Submission status: Accepted

Solution code:

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

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

def cn(n,x):
    return n-(n//x)

def cnt(a,b,x):
    return cn(b,x) - cn(a-1,x)

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

# print(E)
# print(cnt(A,B,C))
# print(cnt(A,B,D))
# print(cnt(A,B,E))

print(cnt(A,B,C)+cnt(A,B,D)-cnt(A,B,E))

Submission status: Accepted

Solution code:
from fractions import gcd

def main():
    A, B, C, D = map(int, input().split())
    ans = 0
    ans += B - ((B // C) + (B // D) - (B // (lcm(C, D))))
    ans -= (A-1) - (((A-1) // C) + ((A-1) // D) - ((A-1) // (lcm(C, D))))
    print(ans)

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

main()

Submission status: Accepted

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
A,B,C,D=map(int,input().split())
A=A-1
# 1<= A-1 patern
AnC=A//C
AnD=A//D
AnCandD=A//lcm(C,D)
Aans=A-(AnC+AnD-AnCandD)
# 1<= B patern
BnC=B//C
BnD=B//D
BnCandD=B//lcm(C,D)
Bans=B-(BnC+BnD-BnCandD)

print(Bans-Aans)

Submission status: Accepted

Solution code:
import sys
import fractions

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def main():
    A, B, C, D = MAP()
    E = lcm(C, D)
    nc = (B // C) - ((A - 1) // C)
    nd = (B // D) - ((A - 1) // D)
    ne = (B // E) - ((A - 1) // E)
    print(B - A + 1 - (nc + nd - ne))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

al = B-A+1

dic = B//C - (A-1)//C
did = B//D - (A-1)//D

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

dicd = B//(lcs) - (A-1)//(lcs)

ans = al - (dic + did - dicd)

print(ans)

Submission status: Accepted

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

def count(N,a,b):
    a_c = N//a+1
    b_c = N//b+1
    lcm = a*b//gcd(a,b)
    ab_c = N//lcm+1
    return a_c+b_c-ab_c

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

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)




c_w = B//C

if A%C==0:
    c_w -= A//C - 1
if A%C!=0:
    c_w -= A//C 
d_w = B//D

if A%D==0:
    d_w -= A//D - 1
if A%D!=0:
    d_w -= A//D

E = lcm(C,D)

cd_w = B//E

if A%E==0:
    cd_w -= A//E - 1
if A%D!=0:
    cd_w -= A//E

# print(c_w,d_w,cd_w)
print(B-A+1-c_w-d_w+cd_w)

Submission status: Accepted

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

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

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

def count(a, b, c):
    d = a // b
    e = a // c
    f = a // lcm(b, c)
    return a - d - e + f
ans = count(b, c, d) - count(a, c, d)
if(a % c != 0 and a % d != 0):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
def solve(a,b,n):
    if a == b:
        if a%n==0:
            return 1
        else:
            return 0
    elif a%n == 0:
        return b//n-a//n+1
    elif b%n==0:
        return b//n-a//n
    else:
        return b//n-a//n

print(b-a+1-(solve(a,b,c)+solve(a,b,d)-solve(a,b,c*d//gcd(c,d))))

Submission status: Accepted

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

Submission status: Accepted

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

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

z = x * y // 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: Accepted

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


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


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


# 1 to X
def divnum(X, d):
    return X // d


divC = divnum(B, C) - divnum(A - 1, C)
divD = divnum(B, D) - divnum(A - 1, D)
divCD = divnum(B, lcm(C, D)) - divnum(A - 1, lcm(C, D))

print(ans - divC - divD + divCD)

Submission status: Accepted

Solution code:
import fractions

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

ac_div, ac_mod = divmod(A-1, C)
ad_div, ad_mod = divmod(A-1, D)
ae_div, ae_mod = divmod(A-1, int(C*D / fractions.gcd(C, D)))
bc_div, bc_mod = divmod(B, C)
bd_div, bd_mod = divmod(B, D)
be_div, be_mod = divmod(B, int(C*D / fractions.gcd(C, D)))

ret = B - A + 1 - (bc_div - ac_div) - (bd_div - ad_div) + (be_div - ae_div)

print(ret)

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split())
A-=1
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x
lCD=C*D//gcd(C,D)
print(B-B//C-B//D+B//lCD-(A-A//C-A//D+A//lCD))