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:
a, b, c, d = [int(e) for e in input().split()]

def gcd(a, b):
  while True:
    t = b % a
    if t == 0:
      return a
    b, a = a, t

def f(a, b, n):
  return b // n - (a - 1) // n

acc = 0
acc += f(a, b, c)
acc += f(a, b, d)
acc -= f(a, b, c * d // gcd(c, d))
print(b - a + 1 - acc)

Submission status: Accepted

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

def gcd(a, b):
  while True:
    t = b % a
    if t == 0:
      return a
    b, a = a, t

def f(a, b, n):
  x = (a // n) * n
  if x < a:
    x += n
  if x > b:
    return 0
  result = 0
  if a <= x <= b:
    result += 1
  result += (b - x) // n
  return result

acc = 0
acc += f(a, b, c)
acc += f(a, b, d)
acc -= f(a, b, c * d // gcd(c, d))
print(b - a + 1 - acc)

Submission status: Accepted

Solution code:
#ABC131 C
import fractions

A, B, C, D = map(int, input().split())
def ad(X):
    XmodC = int(X // C)
    XmodD = int(X // D)
    CD_lcm = int(C * D / fractions.gcd(C, D))
    XmodCD = int(X // CD_lcm)
    return X - (XmodC + XmodD - XmodCD)
ans = ad(B) - ad(A - 1)
print(ans)

Submission status: Accepted

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

c_a, c_b = (a-1)//c, b//c
c_ab = c_b - c_a 

d_a, d_b = (a-1)//d, b//d
d_ab = d_b - d_a 

e_a, e_b = (a-1)//e, b//e
e_ab = e_b - e_a

ans = (b - a + 1) - (c_ab + d_ab - e_ab)
print(ans)

Submission status: Accepted

Solution code:

def gcd(m, n):
    if(n == 0):
        return m
    return gcd(n, m % n)


(a, b, c, d) = [int(i) for i in input().split()]
c_d_lcm = (c * d) // gcd(c, d)
able_c_div = b // c - (a - 1) // c
able_d_div = b // d - (a - 1) // d
able_c_d_div = b // c_d_lcm - (a - 1) // c_d_lcm
diff = b - (a - 1)
print(diff - (able_c_div + able_d_div - able_c_d_div))

Submission status: Accepted

Solution code:
def g_c_d(x, y):
    if y == 0:
        return x
    else:
        return g_c_d(y, x % y)


def l_c_m(x, y):
    return x * y // g_c_d(x, y)


a, b, c, d = map(int, input().split())
e = l_c_m(c, d)
f = b // c - (a - 1) // c + b // d - (a - 1) // d - (b // e - (a - 1) // e)
print(b - a + 1 - f)

Submission status: Accepted

Solution code:
import fractions

def lcm(p,q):
    return (p*q) // fractions.gcd(p,q)

def g(x,k):
    return x // k

def f(x,c,d):
    return x - (g(x,c)+g(x,d)-g(x,lcm(c,d)))

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

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

Submission status: Accepted

Solution code:
import numpy as np
from fractions import gcd

def lcm(x, y):
    return x * y // gcd(x, y)
A, B, C, D = [int(x) for x in input().split(" ")]
n_targets = B - A + 1

n_compC = n_targets - (B // C - (A - 1) // C)
n_compD = n_targets - (B // D - (A - 1) // D)
n_compCandD = n_targets - (B // lcm(C, D) - (A - 1) // lcm(C, D))

print(n_compC + n_compD - n_compCandD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#ABC131C
import sys

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

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

tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
a=hoge[0]
b=hoge[1]
c=hoge[2]
d=hoge[3]

total=b-a+1

csum=(b//c-(a-1)//c)
total-=csum

dsum=(b//d-(a-1)//d)
total-=dsum

cdlcm=lcm(c,d)
cdsum=(b//cdlcm-(a-1)//cdlcm)
total+=cdsum

print(total)

Submission status: Accepted

Solution code:
def main():
    A, B, C, D = list(map(int, input().split()))
    candiv_C = num_can_div(A, B, C)
    candiv_D = num_can_div(A, B, D)
    candiv_lcm = num_can_div(A, B, lcm(C, D))

    print(B-A+1 - candiv_C - candiv_D + candiv_lcm)

def num_can_div(A, B, x):
    return B//x - (A-1)//x

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

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

main()

Submission status: Accepted

Solution code:
# 包除原理, cとdの最小公倍数, b-aではなく b-(a-1)に注意 

def gcd(x, y):
  if x > y:
    return gcd(y, x)
  while x != 0:
    x, y = y % x, x
  return y
def lcm(x, y):
  return (x*y)//gcd(x, y)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import fractions


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

    C_D = (C * D) // fractions.gcd(C, D)

    z = B//C_D - A//C_D

    if A % C == 0:
        x = (B//C) - (A//C) + 1
    else:
        x = (B//C) - (A//C)

    y = B//D - A//D

    print((B-A+1)-(x+y-z))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import *
from sys import *
import math
import queue
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)

#s[i] is linked with t[len(s)-i-1]
def main():
	a,b,c,d = map(int,input().split())
	n = c * d // gcd(c,d)
	a-=1
	ans_b = b - (b//c + b//d - b//n)
	ans_a = a - (a//c + a//d - a//n)
	print(ans_b - ans_a)


def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Accepted

Solution code:
def eratosthenes(a, b):
    if a < b:
        return eratosthenes(b, a)
    while a%b != 0:
        temp = b
        b = a%b
        a = temp

    return b


def lcm(a, b):
    return int(a * b / eratosthenes(a, b))


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

count = B - A + 1
count -= B // C - (A-1) // C
count -= B // D - (A-1) // D
L = lcm(C, D)
count += B // L - (A-1) // L

print(count)

Submission status: Accepted

Solution code:
# x 以下でc, d 両方で割れない条件を満たす自然数の個数をf(x, c, d) とすると
# 求める値は f(b, c, d) - f(a-1, c, d)
# x 以下でk で割れる自然数の個数を g(x, k)とすれば
# f(x, c, d) = x - (g(x, c) + g(x, d) - g(x, lcm(c,d)))
# よって計算すべきは
# g(b, c) + g(b, d) - g(b, lcm(c,d)) - ( g(a-1, c) + g(a-1, d) - g(a-1, lcm(c,d)))
 
def gcd (p, q):
    temp = max(p, q)
    q = min(p, q)
    p = temp
    if q == 0:
        return p
    else:
        return gcd(q, p%q)
    
def lcm(p, q):
    return p * q // gcd(p, q)
 
def g(x, k):
    return x//k
 
def f(x, c, d):
    return x - (g(x, c) + g(x, d) - g(x, lcm(c,d)))
 
a,b,c,d = list(map(lambda x:int(x) ,input().split()))
 
print(f(b, c, d) - f(a-1, c, d))

Submission status: Accepted

Solution code:
A, B, C, D = [int(_) for _ 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)

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

ans = dvi_num2(B, C, D) - dvi_num2(A - 1, C, D)
print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd


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


A, B, C, D = space()
E = int(C * D / gcd(C, D))

c = B // C - (A-1) // C
d = B // D - (A-1) // D
e = B // E - (A-1) // E

print(1 + B - A - (c + d - e))

Submission status: Accepted

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

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

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a%b)

def f(a, b, c):
	leftc = a + (c - a % c) % c
	if leftc > b:
		s = 0
	else:
		rightc = b - b % c
		s = (rightc - leftc) // c + 1
	return s

def F(x, c, d):
	res = x
	res -= x // c
	res -= x // d
	res += x // lcs(c, d)
	return res

# a~bまで→　F(b) - F(a-1)と考える（定積分のイメージ）
def main():
	a, b, c, d = map(int, input().strip().split())
	print(F(b, c, d) - F(a-1, c, d))
	# s = f(a, b, c)
	# t = f(a, b, d)
	# u = f(a, b, lcs(c, d))
	# # print(n,s, t, u)
	# print(n - (s + t - u))

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a%b)

def f(a, b, c):
	leftc = a + (c - a % c) % c
	if leftc > b:
		s = 0
	else:
		rightc = b - b % c
		s = (rightc - leftc) // c + 1
	return s

def main():
	a, b, c, d = map(int, input().strip().split())
	n = b-a+1
	s = f(a, b, c)
	t = f(a, b, d)
	u = f(a, b, lcs(c, d))
	# print(n,s, t, u)
	print(n - (s + t - u))

if __name__ == '__main__':
	main()

Submission status: Accepted

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

def f(x,y,p):
    res = 0
    if x%p == 0:
        start = x+1
        res += 1
    else:
        start = (x//p+1)*p
        if start > y:
            return 0
        if start == y:
            return 1
        start += 1
        res += 1
    return res+(y-start+1)//p

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

#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

#a*x+b*y=gcd(a,b)の一つの解
def extgcd_2(a,b):    
    g = gcd(a,b)
    a = a//g
    b = b//g
    return extgcd(a,b)

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

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

Submission status: Accepted

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

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

def div(a, b, x):
    if a%x!=0:
        return b//x-a//x
    else:
        return b//x-(a//x-1)

print(int(b-a+1-(div(a,b,c)+div(a,b,d)-div(a,b,lcm(c,d)))))

Submission status: Accepted

Solution code:
import fractions

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

mc = b // c
md = b // d
mcd = b // ((c * d) // (fractions.gcd(c, d)))

mb = b - mc - md + mcd

amc = (a - 1) // c
amd = (a - 1) // d
amcd = (a - 1) // ((c * d) // fractions.gcd(c, d))

ma = (a - 1) - amc - amd + amcd

print(int(mb - ma))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

# e = lcm(c,d)
e = c*d//fractions.gcd(c,d)
nc_d = b//e-(a-1)//e
print(b-a+1-nc-nd+nc_d)

Submission status: Accepted

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

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

def div_num(a,x,y):
    return a//x + a//y - a//lcm(x,y)

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

ans = (b-a+1) - ( div_num(b,c,d) - div_num((a-1),c,d) )

print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
from fractions import gcd

def lcm(a, b):
    """ aとbの最小公倍数を返す """
    return a*b // gcd(a, b)

def f(a, x, y):
    """ a以下で、xでもyでも割り切れないものの数"""
    return a - (a//x + a//y - a//lcm(x,y))

def solve():
    A,B,C,D = list(map(int, input().split()))
    ans = f(B, C, D) - f(A-1, C, D)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

C_mod0 = B//C - (A-1)//C
D_mod0 = B//D - (A-1)//D
i = D
j = C % D
while j > 0:
    k = j
    j = i % j
    i = k

CD_mod0 = B*i // (C*D) - (A-1)*i // (C*D)
Total = B - A + 1
ans = Total - C_mod0 - D_mod0 + CD_mod0

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a, b, c, d  = map(int,input().split())
def divbyk(k):
    return    b//k-(a-1)//k

def gcd(x,y):
    n = min(x,y)
    m = max(x,y)
    if n == 0:
        return m
    else:
        return round(gcd(n,m-(m//n)*n))

ans = b-(a-1) - divbyk(c) - divbyk(d) + divbyk(c*d//gcd(c,d))
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

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

cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
s=b//(c*d//fractions.gcd(c,d))-(a-1)//(c*d//fractions.gcd(c,d))


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

Submission status: Accepted

Solution code:
from fractions import gcd


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

cc = B // C - (A - 1) // C
dd = B // D - (A - 1) // D
lcm = C * D // gcd(C, D)
cd = B // lcm - (A - 1) // lcm
ans = (B - A + 1) - cc - dd + cd
print(ans)

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

Submission status: Accepted

Solution code:
# 	i+=1


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

cer=b//c-a//c
der=b//d-a//d
if(a%c==0):
	cer+=1
if(a%d==0):
	der+=1
def gcd(a,b):
	if(b==0):
		return a
	else:
		return gcd(b,a%b)
newno=int((c*d)/gcd(c,d))
newer=b//newno-a//newno
if(a%newno==0):
	newer+=1
print(b-a+1-cer-der+newer)

Submission status: Accepted

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

def calc(n):
    return (B // n) - ((A - 1) // n)

def lcm(c, d):
    a, b = c, d
    if c < d:
        a, b = d, c
    while b != 0:
        a, b = b, a % b

    return c * d // a

E = lcm(C, D)
print(calc(1) -calc(C)-calc(D)+calc(E) )

Submission status: Accepted

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


com=lcm(c, d)
tmp=(b-b//com)-(a-a//com)
print(count-tmp)

Submission status: Accepted

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

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

def f(b, c, d):
  return b - ((b // c) + (b // d)) + b // ((c * d) // gcd(c,d))

print(f(b, c, d) - f(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

lcm = C * D // gcd(C, D)
total = B - A + 1
ans = total - ((B // C - (A - 1) // C) + (B // D - (A - 1) // D) - (B // lcm - (A - 1) // lcm))
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#gcd関数(最大公約数を求める)
from fractions import gcd
a,b,c,d = map(int,input().split())
 
#c,dにおける最小公倍数を求める
z = c*d // gcd(c,d)
#a - 1以下の個数を求める
i = a - 1

#xはb以下で割り切れない個数を求める
x = b - (b // c + b // d - b // z)
#yはa - 1以下で割り切れない個数を求める
y = i - (i // c + i // d - i // z)
#b以下で割り切れない個数からa- 1以下で割り切れない個数引いた個数
print(x - y)

Submission status: Accepted

Solution code:
def C_AntiDivision():
    from sys import version_info
    try:
        from math import gcd
    except:
        from fractions import gcd
    a,b,c,d = map(int, input().split())
    total = b - a + 1
    total_c = (b // c) + (-a // c) + 1
    total_d = (b // d) + (-a // d) + 1
    gcd_cd = c*d // gcd(c,d)
    total_cd = (b // gcd_cd) + (-a // gcd_cd) + 1
    #print(total_c, total_d, total_cd, gcd_cd)
    print(int(total - total_c - total_d + total_cd))

if __name__ == "__main__":
    C_AntiDivision()

Submission status: Accepted

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

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

def F(a, c, d):
    x = a - a//c - a//d + a//lcm(c, d)
    return x

ans = int(F(B, C, D) - F(A-1, C, D))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


def solve(string):
    a, b, c, d = map(int, string.split())
    _gcd = gcd(c, d)
    lcm = (c // _gcd) * (d // _gcd) * _gcd
    return str(b - a + 1 - (b // c - (a - 1) // c + b // d - (a - 1) // d - b // lcm +
               (a - 1) // lcm))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
if(A % C == 0):
    c_div = (B // C) - (A // C) + 1
else:
    c_div = (B // C) - (A // C + 1) + 1
if(A % D == 0):
    d_div = (B // D) - (A // D) + 1
else:
    d_div = (B // D) - (A // D + 1) + 1
cd_lcm = (C * D) // gcd(C, D)
if(A % cd_lcm == 0):
    cd_div = (B // cd_lcm) - (A // cd_lcm) + 1
else:
    cd_div = (B // cd_lcm) - (A // cd_lcm + 1) + 1
print((B - A) - (c_div + d_div - cd_div) + 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())
a -= 1
print(b-(b//c+b//d-b//lcm(c,d))-\
     a+(a//c+a//d-a//lcm(c,d)))

Submission status: Accepted

Solution code:
import fractions 

# 01:10
A, B, C, D = tuple([int(a) for a in input().split(' ')])


def func1(n):
    return n - n//C - n//D + n//(C*D//fractions.gcd(C, D))


print(func1(B) - func1(A-1))

Submission status: Accepted

Solution code:
A,B,C,D = map(int,input().split())
pBC = B//C
pAC = (A-1)//C
pBD = B//D
pAD = (A-1)//D
def gcd(a,b):
  while b!=0:
    a,b = b,a%b
  return a
def lcm(a,b):
  return a*b//gcd(a,b)
CDlcm = lcm(C,D)
pBCD = B//CDlcm
pACD = (A-1)//CDlcm
ans =(B - A + 1) - ((pBC - pAC) + (pBD - pAD) - (pBCD - pACD))
print(ans)

Submission status: Accepted

Solution code:
import fractions

def x(k, c, d):
    rl1 = k
    lcm = c*d // fractions.gcd(c,d)
    ccount = rl1 // c
    dcount = rl1 // d
    cdcount = rl1 // lcm
    # if lcm != 0:
    #     cdcount = int(rl1 // lcm)
    # else:
    #     cdcount = 0

    return rl1 - ccount - dcount + cdcount

a, b, C, D = map(int, input().split())
print(x(b, C, D) - x(a-1, C, D))

Submission status: Accepted

Solution code:
import io
import sys
from fractions import gcd


def IN_S():
  return input()


def IN_I():
  return int(input())


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


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


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
314159265358979323 846264338327950288 419716939 937510582
'''


def MAIN():
  # T_IN()
  A()


def A():
  a, b, c, d = IN_L_I()

  divc = (b // c) - ((a - 1) // c)
  divd = (b // d) - ((a - 1) // d)
  cd = c * d // gcd(c, d)
  divcd = (b // cd) - ((a - 1) // cd)


  total = (b + 1 - a) - divc - divd + divcd

  print(total)
  return None
 

def B():
  return None


def C():
  return None


MAIN()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

A,B,C,D = LI()

'''
cでもdでも割り切れない
逆に割り切れる数を計算する
Bまでで割り切れる個数
Aまでで割り切れる個数
B'-A'でA-Bまでの割り切れる個数が出せる
'''
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

BC = B//C
BD = B//D
BCD = B//lcm(C,D)

#  print('BC, BD, BCD', BC, BD, BCD)
B_count = B - (BC + BD - BCD)

A = A - 1
AC = A//C
AD = A//D
ACD = A//lcm(C,D)
#  print('AC, AD, ACD', AC, AD, ACD)

A_count = A - (AC + AD - ACD)

#  print(B_count, A_count)
print(B_count - A_count)

Submission status: Accepted

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

lcm = (C*D) // fractions.gcd(C,D)
Bnondiv = B - (B//C + B//D - B//lcm)
Anondiv = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//lcm)
print(int(Bnondiv-Anondiv))

Submission status: Accepted

Solution code:
a, b, c, d= map(int, input().split())
def gcd(c,d):
    if c%d == 0:
        return d
    else:
        return gcd(d,c%d)
def num(n,c,d):
    lcm = c // gcd(c, d) * d
    return n - n//c - n//d + n//lcm
print(num(b,c,d)-num(a-1,c,d))

Submission status: Accepted

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


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

if(a%c==0):
    first = (b//c) - (a//c)+1
else:
    first = (b//c) - (a//c)
if(a%d==0):
    second = (b//d) - (a//d) + 1
else:
    second = (b//d) - (a//d)
lcm = (c*d)//gcd(c,d)
if(a%lcm==0):
    common = (b//lcm) - (a//lcm) + 1
else:
    common = (b//lcm) - (a//lcm)
print((b-a+1)-(first+second-common))

Submission status: Accepted

Solution code:
from fractions import gcd

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


def cnt_div(a, b, x):
    q, r = divmod(a, x)

    if r == 0:
        m = q - 1
    else:
        m = q

    n = b // x

    return n - m


num_c = cnt_div(a, b, c)
num_d = cnt_div(a, b, d)
lcm = int((c * d) / gcd(c, d))
num_c_d_gcd = cnt_div(a, b, lcm)

print((b - a + 1) - (num_c + num_d - num_c_d_gcd))

Submission status: Accepted

Solution code:
import math
from fractions import gcd

def count(n, A, B):
    n_upper = B // n
    n_lower = (A-1) // n
    n_count = n_upper - n_lower
    return n_count

def main():
    A, B, C ,D  = list(map(int, input().split(" ")))
    C_count = count(C, A, B)
    D_count = count(D, A, B)
    s = (C * D) // gcd(C, D)
    CD_count = count(s, A ,B)
    fcount = (B - A + 1) - (C_count + D_count - CD_count)
    print(fcount)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

a, b, c, d = wi()

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

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
#532105071133627368

s = ((a + c - 1) // c) * c
t = (b // c) * c
kosu1 = (t - s) // c + 1

u = ((a + d - 1) // d) * d
v = (b // d) * d
kosu2 = (v - u) // d + 1

e = lcm_base(c, d)
w = ((a + e - 1) // e) * e
x = (b // e) * e
kosu3 = (x - w) // e + 1

print(b - a + 1 - (kosu1 + kosu2 - kosu3))

Submission status: Accepted

Solution code:
from fractions import gcd

a, b, c, d = map(int, input().split())
l = c * d // gcd(c, d)

f = lambda n: n - (n // c + n // d - n // l)

print(f(b) - f(a - 1))

Submission status: Accepted

Solution code:
import fractions

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

U = B - A + 1

def number(R):
        return ((B // R) - ((A - 1) // R))

possible_C = number(C)
possible_D = number(D)
possible_CD = number((C * D) // fractions.gcd(C, D))

print(U - (possible_C + possible_D) + possible_CD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
from fractions import gcd

def f(a, x):
    # 1~a以下の数で、xで割り切れるものの数を返す
    return a//x


def lcm(a, b):
    """ aとbの最小公倍数を返す """
    return a*b // gcd(a, b)


def solve():
    A,B,C,D = list(map(int, input().split()))
    A -= 1
    ans = (B - (f(B,C)+f(B,D)-f(B,lcm(C,D)))) - (A - (f(A,C)+f(A,D)-f(A,lcm(C,D))))
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#ABC131c 3.4以前ではmathではなくfractons

import fractions

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


count_c=b//c - (a-1)//c
count_d=b//d - (a-1)//d
count_cd=b//(c*d//fractions.gcd(c,d)) - (a-1)//(c*d//fractions.gcd(c,d))

print(b-a+1-count_c-count_d+count_cd)

Submission status: Accepted

Solution code:
def bbb(x, y):
    return (x * y) // aaa(x, y)
 
 
def aaa(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    else:
        return aaa(y, x % y)
 
 
a, b, c, d = map(int, input().split())
bc = b // c
bd = b // d
ac = (a-1) // c
ad = (a-1) // d
aw = (a-1) // bbb(c, d)
bw = b // bbb(c, d)
print((b - a + 1) - (bc - ac) - (bd - ad) + (bw - aw))

Submission status: Accepted

Solution code:
from fractions import gcd

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

def f(n, C, D):
    x = n // C
    y = n // D
    z = n // lcm(C, D)
    return n - x - y + z


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

Submission status: Accepted

Solution code:
from fractions import gcd

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

def f(n, C, D):
    x = n // C
    y = n // D
    z = n // lcm(C, D)
    return n - x - y + z


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

Submission status: Accepted

Solution code:
from fractions import gcd

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


A, B, C, D = map(int, input().split())
s1 = B - (B // C + B // D - B // lcm(C, D))
s2 = A-1 - ((A-1) // C + (A-1) // D - (A-1) // lcm(C, D))
ans = s1 - s2
print(ans)

Submission status: Accepted

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
logging.disable(logging.CRITICAL)


def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        else:
            return z

def main():
    A, B, C_, D_ = (int(x) for x in input().split())

    if C_ > D_:
        C, D = D_, C_
    else:
        C, D = C_, D_
        

    lcm_CD = int(C * D / gcd(C, D))
    
    div_C = int(B // C) - int((A - 1) // C)
    div_D = int(B // D) - int((A - 1) // D)
    div_lcm_CD = int(B // lcm_CD) - int((A - 1) // lcm_CD)
    
    answer = B - A + 1 - div_C - div_D + div_lcm_CD

    if A == 0:
        print(answer - 1)
    else:
        print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bbb(x, y):
    return (x * y) // aaa(x, y)


def aaa(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    else:
        return aaa(y, x % y)


a, b, c, d = map(int, input().split())
bc = b // c
bd = b // d
ac = (a-1) // c
ad = (a-1) // d
aw = (a-1) // bbb(c, d)
bw = b // bbb(c, d)
print((b - a + 1) - (bc - ac) - (bd - ad) + (bw - aw))

Submission status: Accepted

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

#b以下の自然数で、cでもdでも割り切れないものの個数から
#a-1以下の自然数で、cでもdでも割り切れないものの個数を引けばOK

#cとdの最小公倍数を求める
def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)

#b以下の自然数で、cでもdでも割り切れないものの個数を求める
b_ika=b-(b//c+b//d-b//lcm(c,d))
a_mimann=a-1-((a-1)//c+(a-1)//d-(a-1)//lcm(c,d))

ans=b_ika-a_mimann

print(ans)

Submission status: Accepted

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

if C<D:
  c, d = C, D
else:
  c, d = D, C
while d%c!=0:
  c, d = d%c, c
lcm = C*D//c

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

Submission status: Accepted

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

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

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

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 // gcd(a, b) * b


def calc(x, a, b):
    return x - x // a - x // b + x // lcm(a, b)


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

Submission status: Accepted

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

a,b,c,d = map(int, input().split())
x1 = b // c
x2 = b // d
e = lcm(c,d)
x3 = b // e
y1 = b - x1 -x2 + x3
x4 = (a-1) // c
x5 = (a-1) // d
x6 = (a-1) // e
y2 = a -1 - x4 - x5 + x6
print(y1 - y2)