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 gcd(m,n):
    x= max(m,n)
    y= min(m,n)
    if x%y == 0:
        return y
    else:
        while not x%y==0:
            z=x%y
            x= y
            y=z
        else:
            return z
def lcm(x, y):
    return (x * y) // gcd(x, y)


a,b,c,d = map(int,input().split())
lcm = lcm(c,d)
c_i=a//c
d_i=a//d
cd_i=a//lcm
if not a%c==0:
    c_i+=1
if not a%d==0:
    d_i+=1
if not a%lcm==0:
    cd_i+=1

c_f=b//c
d_f=b//d
cd_f=b//lcm

print(b-a-(c_f+d_f-cd_f-c_i-d_i+cd_i+1)+1)

Submission status: Accepted

Solution code:
import fractions

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

A -= 1

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

excluded = A - (A // C + A // D - A // lcm)
num = B - (B // C + B // D - B // lcm)

print(num - excluded)

Submission status: Accepted

Solution code:
import fractions


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


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

AtoB = (B - (A - 1))

divisible_C = (B // C) - ((A - 1) // C)
divisible_D = (B // D) - ((A - 1) // D)

minLcm = lcm(C, D)

divisible_CD = (B // minLcm) - ((A - 1) // minLcm)

divisible_CtoD = (divisible_C + divisible_D) - divisible_CD

answer = AtoB - divisible_CtoD

print(answer)

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
F = fractions.gcd(C,D)
E = C*D//F
if (A%C == 0) or (A%D == 0) :
  print((B-A)-(B//C)-(B//D)+(B//E)+(A//C)+(A//D)-(A//E))
else :
  print((B-A+1)-(B//C)-(B//D)+(B//E)+(A//C)+(A//D)-(A//E))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

b_sum = B - ((B//C) + (B//D) - (B//lcm))

a = A-1
a_sum = a - ((a//C) + (a//D) - (a//lcm))

print(b_sum - a_sum)

Submission status: Accepted

Solution code:
from decimal import *

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

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

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

# Cで割り切れる数
divC = (B // C) - ((A - 1) // C);
# Dで割り切れる数
divD = (B // D) - ((A - 1) // D);
# CでもDでも割り切れる数
CD = lcm(C, D);
divCD = (B // CD) - ((A - 1) // CD); 
# 答え
N = B - A + 1;
result = N - divC - divD + divCD;
print('{:.50g}'.format(result));

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())
E = lcm(C,D)
cnt_C = 0
cnt_D = 0
cnt_E = 0
if A % C == 0:
    cnt_C += 1
if A % D == 0:
    cnt_D += 1
if A % E == 0:
    cnt_E += 1

diff = B-A
cnt_C += (diff+A%C)//C
cnt_D += (diff+A%D)//D
cnt_E += (diff+A%E)//E

print(B-A+1-cnt_C-cnt_D+cnt_E)

Submission status: Accepted

Solution code:
# coding: utf-8
from math import ceil, floor
from fractions import gcd
A, B, C, D = map(int, input().split())
lcm = (C * D) // gcd(C, D)
c_cnt = B // C - (A-1) // C
d_cnt = B // D - (A-1) // D
cd_cnt = B // (lcm) - (A-1) // (lcm)
minus = c_cnt + d_cnt - cd_cnt
print(B - A - minus + 1)

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())
CD = lcm(C,D)
C_num = B//C-A//C+(1 if A%C==0 else 0)
D_num = B//D-A//D+(1 if A%D==0 else 0)
CD_num = B//CD-A//CD+(1 if A%CD==0 else 0)
print(B-A+1-C_num-D_num+CD_num)

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 akarabmadecde(a: int, b: int, c: int):
    if a % c == 0:
        return (b // c) - (a // c) + 1
    else:
        return (b // c) - (a // c + 1) + 1

def main():
    input_str = input()

    a, b, c, d = input_str.split()

    a = int(a)
    b = int(b)
    c = int(c)
    d = int(d)

    x = akarabmadecde(a, b, c)
    y = akarabmadecde(a, b, d)
    z = akarabmadecde(a, b, lcm(c, d))

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

def gcd(i,j):
    i, j = max(i,j), min(i,j)
    if i % j == 0:
        return j
    else:
        while i % j !=0:
            k = i % j
            i, j = j, k
        else:
            return k

def solve(a, b, c, d):
    def how_many(to, divide):
        if to >= divide:
            n = to // divide
        else:
            n = 0
        return n
    count_by_c = how_many(b, c) - how_many(a - 1, c)
    count_by_d = how_many(b, d) - how_many(a - 1, d)
    # print('gcd', int(c*d / math.gcd(c,d)))
    count_by_cd = how_many(b, int(c*d / gcd(c,d))) - how_many(a - 1, int(c*d / gcd(c,d)))
    result = b - a + 1 - (count_by_c + count_by_d - count_by_cd)
    # print(count_by_c,  count_by_d, count_by_cd)

    # print(result)
    return result

def main():
    a, b, c, d = input_from_console()
    print(solve(a, b, c, d))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Accepted

Solution code:

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

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


#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)


sais = lcm(C, D)

buff_a = A - 1


sais_mx = B // sais
sais_mm = buff_a // sais
sais_count = sais_mx - sais_mm
if sais_mx > 0:
    sais_count = sais_mx - sais_mm
else:
    sais_count = 0

# print('sais_mx ' + str(sais_mx))
# print('sais_count ' + str(sais_count))

c_mx = B // C
c_mm = buff_a // C
c_count = c_mx - c_mm

d_mx = B // D
d_mm = buff_a // D
d_count = d_mx - d_mm

# print("c d")
# print(c_count, d_count)
zentai = c_count + d_count

# zentai = zentai - (sais_count*2)
zentai = zentai - (sais_count)

b_a = B - A
ans = b_a - zentai
# print(zentai)
print(ans+1)

Submission status: Accepted

Solution code:
def g(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
from decimal import Decimal
A,B,C,D=map(lambda x:Decimal(int(x)),input().split())



if A%C==0:
    x=B//C-A//C+1
else:
    x=B//C-A//C
if A%D==0:
    y=B//D-A//D+1
else:
    y=B//D-A//D
E=Decimal(C*D//g(C,D))
if A%E==0:
    z=B//E-A//E+1
else:
    z=B//E-A//E
print(B-A+1-(x+y-z))

Submission status: Accepted

Solution code:
a, b, c, d = (int(i) for i in input().split())
e = 0
f = 0
g = 0
h = 0
j = 0
k = 0
l = 0
m = 0
n = 0
o = 0
count = 0

e = -(-a//c)
f = b // c 
g = f - e + 1 #cの倍数の個数

h = -(-a//d)
j = b // d 
k = j - h + 1 #dの倍数の個数

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 lcm(m,n):
  return int(m*n / gcd(m,n))

o = lcm(c,d)
l = -(-a//o)
m = b // o 
n = m - l + 1 #c*dの倍数の個数 

print(b-a+1-g-k+n)

Submission status: Accepted

Solution code:
import math
import fractions

def main():

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

    CD = C * D / fractions.gcd(C,D)
    #print("CD = ", CD)

    count_C = B//C - (A-1)//C
    #print("count_C = ", count_C)

    count_D = B//D - (A-1)//D
    #print("count_D = ", count_D)

    count_CD = B//int(CD) - (A-1)// int(CD)
    #print("count_CD = ", count_CD)

    print(int(B-A+1 - (count_C + count_D - count_CD)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

under_c = (A - 1) // C
under_d = (A - 1) // D
under_cd = (A - 1) // lcm_cd

top_c = B // C
top_d = B // D
top_cd = B // lcm_cd

ans = (B -
       (A - 1)) - (top_c - under_c) - (top_d - under_d) + (top_cd - under_cd)

print(ans)

Submission status: Accepted

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

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

a,b,c,d = list(map(int,input().split(" ")))
e = lcm(c,d)
p=(a-1)//c
o=b//c
i=(a-1)//d
u=b//d
y=(a-1)//e
t=b//e
C = max([0,o-p])
D = max([0,u-i])
E = max([0,t-y])
print( (b-a+1)-(C+D-E) )

Submission status: Accepted

Solution code:
import fractions


def main():
    A, B, C, D = map(int, input().split())
    lcm = (C * D) // fractions.gcd(C, D)
    bc = B // C
    ac = A // C
    if A % C == 0:
        ac -= 1
    bd = B // D
    ad = A // D
    if A % D == 0:
        ad -= 1
    blcm = B // lcm
    alcm = A // lcm
    if A % lcm == 0:
        alcm -= 1
    print(B - A + 1 - ((bc - ac) + (bd - ad) - (blcm - alcm)))


main()

Submission status: Accepted

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
abcd = input().split(" ")
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
cd = lcm(c, d)
print(b-a-(b//c-((a-1)//c + 1))-(b//d - ((a-1)//d + 1))+(b//cd-((a-1)//cd + 1)))

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)

a, b, c, d = map(int, input().split())
c1 = (b // c) - (a // c)
if a % c == 0:
    c1 += 1
d1 = (b // d) - (a // d)
if a % d == 0:
    d1 += 1
lam1 = lcm(c, d)
cd = (b // (lam1)) - (a // (lam1))
if a % lam1 == 0:
    cd += 1
print((b - a + 1) - ((c1 + d1) - cd))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#a = [int(x) for x in input().split()]
a, b, c, d = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
def count(c):
  return b // c - (a-1) // c

def doit():
  res = b + 1 - a
  print(res, file=sys.stderr)
  res -= count(c)
  print(res, file=sys.stderr)
  res -= count(d)
  print(res, file=sys.stderr)
  l = lcm(c, d)
  print(l, file=sys.stderr)
  res += count(l)
  print(res, file=sys.stderr)
  return res

#print(doit([0] * 4))
#doit(s)
#print(doit())
try:
  print(doit())
except Exception as e:
  print("e", e, file=sys.stderr)

Submission status: Accepted

Solution code:
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 lcm(x, y):
    return int((x * y) / gcd(x, y))
a,b,c,d = map(int,input().split())
count = 0
if c == 1 or d == 1:
    print(0)
else:
    lcm = lcm(c,d)
    ans1 = (b // c - (a-1) // c + b // d - (a-1) // d - b // lcm + (a-1) // lcm)
    print(b - a + 1 - ans1)

Submission status: Accepted

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

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


nc = B // C - (A - 1) // C
nd = B // D - (A - 1) // D
CD = C * D // gcd(C, D)
ncd = B // CD - (A - 1) // CD
ans = (B - A + 1) - nc - nd + ncd

print(ans)

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
 
gcd = fractions.gcd(c,d)
lcm= int((c*d)/fractions.gcd(c,d))
a_c = int((a-1)//c)
b_c = int(b//c)
a_d = int((a-1)//d)
b_d = int(b//d)
a_cd = int((a-1)//lcm)
b_cd = int(b//lcm)
 
 
ans = b-a+1-((b_c-a_c)+(b_d-a_d)-((b_cd-a_cd)))
print(int(ans))

Submission status: Accepted

Solution code:
import math
import fractions


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


if __name__ == '__main__':
    a, b, c, d = map(int, input().split())
    warikireru_c = b // c - (- (-a // c)) + 1
    warikireru_d = b // d - (-(-a // d)) + 1
    lcm_1 = lcm(c, d)
    warikireru_lcm = b // lcm_1 - (- (-a // lcm_1)) + 1
    num = b - a + 1
    print(num - (warikireru_c + warikireru_d - warikireru_lcm))

Submission status: Accepted

Solution code:
# coding: utf-8
#a,bの最大公約数
def calcGCD(a, b):
    while b:
        a, b = b, a % b
    return a

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

def countNum(ab, c, d, lcm):
    return ab // c + ab // d - ab // lcm

a, b, c, d = list(map(int, input().split()))
a -= 1
lcm = calcLCM(c, d)
print(b - a - (countNum(b, c, d, lcm) - countNum(a, c, d, lcm)))

Submission status: Accepted

Solution code:
def gcd(c,d):
    if c%d==0:
        return d
    else:
        return gcd(d,c%d)

def lcm(c,d):
    return c*d//gcd(c,d)

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

l = lcm(c,d)
res = 0
bal = b-a+1
print(bal - ( (b//c-(a-1)//c) + (b//d-(a-1)//d) - (b//l-(a-1)//l) ))

Submission status: Accepted

Solution code:
import math
from fractions import gcd
from decimal import *
getcontext().prec = 56

def lcm(x, y):
  a = Decimal(max(x,y)) / Decimal(gcd(x, y))
  b = Decimal(min(x,y)) * Decimal(a)
#    return (x * y) // gcd(x, y)
  return b // 1
  
a,b,c,d = map(Decimal, input().split())

div_c_min = math.ceil(a/c) * c
div_c_max = math.floor(b/c) * c
if div_c_max >= div_c_min:
  div_c_cnt = (div_c_max - div_c_min) / c + 1
else:
  div_c_cnt = 0
  
div_d_min = math.ceil(a/d) * d
div_d_max = math.floor(b/d) * d
if div_d_max >= div_d_min:
  div_d_cnt = (div_d_max - div_d_min) / d + 1
else:
  div_d_cnt = 0

lcm_cd = lcm(c,d)
div_cd_min = math.ceil(a/lcm_cd) * lcm_cd
div_cd_max = math.floor(b/lcm_cd) * lcm_cd
if div_cd_max >= div_cd_min:
  div_cd_cnt = (div_cd_max - div_cd_min) / lcm_cd + 1
else:
  div_cd_cnt = 0

#print(d,c,div_c_cnt,div_d_cnt,div_cd_cnt)
  
print(int(b - a + 1 - (div_c_cnt + div_d_cnt - div_cd_cnt)))

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)

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

bandc = b // c 
bandd = b // d
bandcd = b // lcm(c,d)

aandc = a // c 
aandd = a // d
aandcd = a // lcm(c,d)

totalb = b - bandc - bandd + bandcd
totala = a - aandc - aandd + aandcd
#print(totalb)
#print(totala)
if (a % c != 0) and (a % d != 0):
    ans = totalb - totala + 1
else:
    ans = totalb - totala

print(ans)

Submission status: Accepted

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


a,b,c,d = map(int, input().split())
cnt = 0
ansb1 = b // c
ansb2 = b // d
ansb12 = b // (c*d//(gcd(c,d)))
bb = (ansb1 + ansb2) - ansb12

ansa1 = (a-1) // c
ansa2 = (a-1) // d
ansa12 = (a-1) // (c*d//(gcd(c,d)))
aa = (ansa1 + ansa2) - ansa12
print((b-a+1)-(bb-aa))

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())

A -= 1

E = lcm(C, D)

CBdiv = B // C
DBdiv = B // D
EBdiv = B // E


CAdiv = A // C
DAdiv = A // D
EAdiv = A // E

ans = B - A - ((CBdiv - CAdiv) + (DBdiv - DAdiv) - (EBdiv - EAdiv))

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)

a,b,c,d = input().split(' ')

a = int(a)
b = int(b)
c = int(c)
d = int(d)

hoge = lcm(c,d)

counter = 0

counter = counter + ((b // c) + (b // d) - (b // hoge))
counter = counter - (((a - 1) // c) + ((a - 1) // d) - ((a - 1) // hoge))

print(b - a + 1 - counter)

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())

x = B // C
y = B // D
z = B // lcm(C, D)
num1 = (B - (x + y - z))

x = A // C
y = A // D
z = A // lcm(C, D)
num2 = (A - (x + y - z))
  
num = num1 - num2

if A % C != 0 and A % D != 0:
  num += 1
  
print(num)

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())

c1 = B // C
c2 = (A-1) // C
c = c1 - c2

d1 = B // D
d2 = (A-1) // D
d = d1- d2

numl = lcm(C, D)
num1 = B // numl
num2 = (A-1) // numl
num = num1 - num2

tmp1 = c + d - num
tmp2 = B - A + 1
print(tmp2 - tmp1)

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())
print(
  (B - B // C - B // D + B // lcm(C, D)) - 
  ((A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // lcm(C, D))
)

Submission status: Accepted

Solution code:
import numpy as np
import fractions

def main():
    abcd = list(map(int, input().split(' ')))
    al = abcd[1] - abcd[0] + 1
    cc = abcd[1] // abcd[2] - (abcd[0]-1) // abcd[2]
    dd = abcd[1] // abcd[3] - (abcd[0]-1) // abcd[3]
    skbs = (abcd[2] * abcd[3]) // fractions.gcd(abcd[2], abcd[3])
    dis = cc + dd - (abcd[1] // skbs - (abcd[0]-1) // skbs)
    print(int(al - dis))

if __name__ == "__main__":
    main()

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)


divAC = A // C
divAD = A // D
divACD = A // lcm(C, D)
divBC = B // C
divBD = B // D
divBCD = B // lcm(C, D)

result = 0
if A % C == 0 or A % D == 0:
    result = (B - divBC - divBD + divBCD) - (A - divAC - divAD + divACD)
else:
    result = (B - divBC - divBD + divBCD) - (A - divAC - divAD + divACD) + 1
print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import fractions

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

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


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

    
def main():
    res = 0
    tmp = 0
    if A%C == 0:
        tmp+=1    
    NC = B//C - A//C + tmp
    
    tmp = 0
    if A%D == 0:
        tmp+=1


    ND = B//D - A//D + tmp
    
    tmp=0
    lcm_CD =lcm(C, D)

    if A%lcm_CD == 0:
        tmp+=1
    lcm_CD =lcm(C, D) +tmp
    
    NCD= B//lcm_CD - A//lcm_CD 
    res = B-A+1 -(NC+ND-NCD)
    if res == -1:
        return print(0)
    #print(NC, ND, NCD)        
        
        
        
    
    print(res)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

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


#[1,x]のうちCで割り切れる
def C(x):
    return x // c


#Dで割り切れる
def D(x):
    return x // d


gcd = lambda x, y: gcd(y, x % y) if x % y else y


#CでもDでも割り切れる
def CD(x):
    return x // (c * d // gcd(c, d))


#CまたはDで割り切れる
def CorD(x):
    return C(x) + D(x) - CD(x)


#CでもDでも割り切れない
def CnorD(x):
    return x - CorD(x)


print(CnorD(b) - CnorD(a - 1))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
x=b//c
y=b//d
z=b//(c*d // fractions.gcd(c,d))
xx=(a-1)//c
yy=(a-1)//d
zz=(a-1)//(c*d // fractions.gcd(c,d))
if c==1 or d==1:
    print(0)
elif c==d:
    print(b-x-(a-1-xx))
elif a==b:
    if a%c==0 or a%d==0:
        print(0)
    else:
        print(1)
else:
    print(int(b-x-y+z-(a-1-xx-yy+zz)))

Submission status: Accepted

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

import fractions
ccount = ((B//C*C)-((A-1)//C*C +C))//C +1
dcount = ((B//D*D)-((A-1)//D*D +D))//D +1
lcm = (C * D) // fractions.gcd(C, D)
cdcount = ((B//lcm*lcm)-((A-1)//lcm*lcm +lcm))//lcm +1
count = B - A + 1 - ccount - dcount + cdcount
print(int(count))

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())
U = B - A + 1
S_c = B // C - (A-1) // C
S_d = B // D - (A-1) // D
S_cd = B // (C * D // fractions.gcd(C, D)) - ((A-1) // (C * D // fractions.gcd(C, D)))
print(U - S_c - S_d + S_cd)

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())

a = (A - 1) // C
b = B // C

c = (A - 1) // D
d = B // D

l = lcm(C, D)

e = (A - 1) // l
f = B // l
    
res = (B - A + 1) - ((b - a) + (d - c) - (f - e))

print(res)

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))

C_comp = (B//C) - ((A-1)//C)
D_comp = (B//D) - ((A-1)//D)
CD_comp = (B//lcm(C,D)) - ((A-1)//lcm(C,D))

print((B - A + 1) - (C_comp + D_comp - CD_comp))

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        temp = a
        a = b
        b = temp

    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b

    return b


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

c_st = (A-1) // C
c_end = B // C
c_num = c_end - c_st

d_st = (A-1) // D
d_end = B // D
d_num = d_end - d_st

E = (C * D) // gcd(C, D)
e_st = (A-1) // E
e_end = B // E
e_num = e_end - e_st

ans = B - A - c_num - d_num + e_num + 1

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
A, B, C, D = map(int, input().split())
if C == 1 or D == 1:
  print(0)
  exit()

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

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

result = 0

if A%C == 0 or A%D == 0:
  A += 1

result += (B-A+1) - (B//C - A//C) - (B//D - A//D)
l = lcm(C, D)
result += (B//l - A//l)

print("{}".format(result))

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = [int(i) for i in input().split()]
gcd = c * d // fractions.gcd(c, d)
num = b - a + 1
num -= b // c - (a - 1) // c
num -= b // d - (a - 1) // d
num += b // gcd - (a - 1) // gcd
print(num)

Submission status: Accepted

Solution code:
from decimal import Decimal

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


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

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

#print('{:.100g}'.format(G))

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

print ('{:.100g}'.format(B - A + 1 - ans))

Submission status: Accepted

Solution code:
import fractions

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

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

C_bot = C * -(-A//C) 
C_top = C * (B//C) 
D_bot = D * -(-A//D)
D_top = D * (B//D)
CD_bot = lcm_CD * -(-A//(lcm_CD ))
CD_top = lcm_CD  * (B//(lcm_CD ))

num_A_B = B - A + 1
num_divC = (C_top - C_bot)//C + 1
num_divD = (D_top - D_bot)//D + 1
num_divCD = (CD_top - CD_bot)//(lcm_CD ) + 1
ans = num_A_B - num_divC - num_divD + num_divCD


print(int(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)

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

dif = b - a + 1

# divC = dif // c
# divD = dif // d
divC = 0
divD = 0

if a % c == 0:
    CF = a
else:
    CF = a + (c - (a % c))

if a % d == 0:
    DF = a
else:
    DF = a + (d - (a % d))

divC = (b - CF) // c + 1
divD = (b - DF) // d + 1


kobai = lcm(c, d)
if a % kobai == 0:
    KF = a
else:
    KF = a + (kobai - (a % kobai))

#divKobai = dif // kobai
divKobai = (b - KF) // kobai + 1

# print('# divC: ' + str(divC))
# print('# divD: ' + str(divD))
#print(divKobai)
print(dif - (divC + divD - divKobai))

Submission status: Accepted

Solution code:
import fractions

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

sum1=(A-1)//C
sum2=B//C
sum3=sum2-sum1
sum1=(A-1)//D
sum2=B//D
sum4=sum2-sum1
num=(C*D)//fractions.gcd(C,D)
sum1=(A-1)//num
sum2=B//num
sum5=sum2-sum1
sum=sum3+sum4-sum5
sum=B-A+1-sum


print(sum)

Submission status: Accepted

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

def main():
    a, b, c, d = map(int, input().split())
    ans = b - a + 1
    if a%c: ans -= b//c-a//c
    else: ans -= b//c+1-a//c

    if a%d: ans -= b//d-a//d
    else: ans -= b//d+1-a//d

    sks = (c*d) // gcd(c, d)
    if a%sks: ans += b//sks-a//sks
    else: ans += b//sks+1-a//sks
    print(ans)

if __name__=="__main__": main()

Submission status: Accepted

Solution code:
def sol(inp=input):
    a,b,c,d=map(int,inp().split())
    def gcd(x,y):
        while y>0:
            x,y=y,x%y
        return x
    def fix_min(b):
        c_=b//c
        d_=b//d
        cd_=b//(c*d//gcd(c,d))
        return b-c_-d_+cd_
    return fix_min(b)-fix_min(a-1)
print(sol())

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
lcm_num = lcm
A, B, C, D = map(int, input().split())

lcm_num = lcm(C, D)

if A%C == 0:
    cnt_c = A//C - 1
else:
    cnt_c = A//C

if A%D == 0:
    cnt_d = A//D - 1
else:
    cnt_d = A//D

if A%(lcm_num) == 0:
    cnt_cd = A//(lcm_num) - 1
else:
    cnt_cd = A//(lcm_num)



num = (B//C)+(B//D)-(B//(lcm_num)) - (cnt_c + cnt_d - cnt_cd)
print(B-A+1-num)

Submission status: Accepted

Solution code:
import fractions
import math

def main():
    buf = input()
    buflist = buf.split()
    A = int(buflist[0])
    B = int(buflist[1])
    C = int(buflist[2])
    D = int(buflist[3])
    l = (C * D) // fractions.gcd(C, D)
    cA = A // C * C + (0 if A % C == 0 else C)
    cB = B // C * C
    c_count = max(0, (cB - cA) // C + 1)
    dA = A // D * D + (0 if A % D == 0 else D)
    dB = B // D * D
    d_count = max(0, (dB - dA) // D + 1)
    lA = A // l * l + (0 if A % l == 0 else l)
    lB = B // l * l
    l_count = max(0, (lB - lA) // l + 1)
    selected = c_count + d_count - l_count
    unselected = (B - A + 1) - selected
    print(unselected)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions

def antidiv(x,l,c,d):
    if x == l or x < 0:
        return l - (l // c) - (l // d) + 1
    else:
        return x - (x // c) - (x // d) 

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

l = (c*d)//fractions.gcd(c,d)


aq = a // l
ar = a % l
bq = b // l
br = b % l
#print(br)

qq = bq - aq - 1
r1 = antidiv(l,l,c,d) - antidiv(ar-1,l,c,d)
r2 = antidiv(br,l,c,d)

if ar!=0:
    ans = qq * antidiv(l,l,c,d) + r1 + r2
else:
    ans = (qq+1) * antidiv(l,l,c,d) + r1 + r2


print(ans)

Submission status: Accepted

Solution code:
import fractions

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

s = B - A + 1

if A % C == 0 or A % D == 0:
    A -= 1

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

E = lcm(C, D)

val1 = A // C
val2 = B // C
val3 = A // D
val4 = B // D
val5 = A // E
val6 = B // E

print(s - (val2 - val1 + val4 - val3 - (val6 - val5)))

Submission status: Accepted

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

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

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

count1 = (B // C - A // C)
count2 = (B // D - A // D)
count3 = (B // CD - A // CD)

if A % C == 0:
    count1 += 1

if A % D == 0:
    count2 += 1

if A % CD == 0:
    count3 += 1 

print(B - A + 1 - ((count1 + count2) - count3))