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:
import math
a,b,c,d=map(int,input().split())
cd = c*d // math.gcd(c,d)
# b以下のc,d,cdの倍数の個数からa未満のc,d,cdの倍数個数をそれぞれ引く
s_c = b//c - (a-1)//c
s_d = b//d - (a-1)//d
s_cd = b//cd - (a-1)//cd
print((b-a+1)-s_c-s_d+s_cd)

Submission status: Accepted

Solution code:
import math

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

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

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

print(B - a - c - d + e)

Submission status: Accepted

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

if A%C==0:
    c=B//C-A//C+1
else:
    c=B//C-A//C

if A%D==0:
    d=B//D-A//D+1
else:
    d=B//D-A//D

def gcd(C,D):
    a=min([C,D])
    b=max([C,D])
    tmp=a
    a=b%a
    b=tmp
    if a==0:
        return tmp
    else:
        return gcd(a,b)

CD=C*D//gcd(C,D)
if A%CD==0:
    cd=B//CD-A//CD+1
else:
    cd=B//CD-A//CD

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

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
L = C*D//(math.gcd(C, D))
C_div = B//C-(A-1)//C
D_div = B//D-(A-1)//D
L_div = B//L-(A-1)//L
print(B-A+1-(C_div+D_div-L_div))

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
L = C * D //math.gcd(C, D)
x = (A - 1) - (A -1) // C - (A - 1) // D + (A - 1) //L
y = B - B // C - B // D + B // L
print(y - x)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
import math
ans=b-a+1
e=(b//c)-(a-1)//c
f=(b//d)-(a-1)//d
g=(b//(c*d//math.gcd(c,d)))-((a-1)//(c*d//math.gcd(c,d)))
h=int(e+f-g)
print(ans-h)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
c = B // C - A // C + int(A % C == 0)
d = B // D - A // D + int(A % D == 0)
E = int((C * D) / math.gcd(C, D))
e = B // E - A // E + int(A % E == 0)
print(B - A + 1 - c - d + e)

Submission status: Accepted

Solution code:
import math
def main():
    a,b,c,d = map(int,input().split())
    bc = b // c
    bd = b // d
    bx = b // (c * d // math.gcd(c,d))
    B = b - bc - bd + bx
    
    a -= 1
    ac = a // c
    ad = a // d
    ax = a // (c * d // math.gcd(c,d))
    A = a - ac - ad + ax
    
    print(B-A)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

#a-bの間の数字の個数（"全体の個数"）を数える
    kosuu = b - a + 1
    
#c, d, c&dの最小公倍数と、a, bそれぞれの割り算の商を求めておく
    a_c = a // c
    a_d = a // d 
    b_c = b // c
    b_d = b // d
    
    lcm_cd = int(c// math.gcd(c,d) * d)
    a_cd = int(a // lcm_cd)
    b_cd = int(b // lcm_cd)

#c, d, c&dの最小公倍数がa, bの間に何個あるか（"約数の個数"）を数える（aは「a以上」の条件から検討に入れるべき数字のため、aで割り切れる場合は約数の個数として含める）
    if a % c == 0:
        kosuu_c = b_c - a_c + 1
    else:
        kosuu_c = b_c - a_c
    
    if a % d == 0:
        kosuu_d = b_d - a_d + 1
    else:
        kosuu_d = b_d - a_d

    if a % lcm_cd == 0:
        kosuu_cd = b_cd - a_cd + 1
    else:
        kosuu_cd = b_cd - a_cd

#全体の個数から約数の個数を引く。公倍数の約数の個数分多く引きすぎているため、足し戻す
    print(kosuu - kosuu_c - kosuu_d +kosuu_cd)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

bf = b//f2
af = (a-1)//f2

cb = b//c
ca = (a-1)//c

db = b//d
da = (a-1)//d

print(b-a+1-(cb-ca)-(db-da)+(bf-af))

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

from fractions import gcd

A, B, C, D = rl()

def f(n, d):
	return n // d

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

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

Submission status: Accepted

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

Submission status: Accepted

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

l1 = a % c
r1 = b % c

if l1 > r1:
    cnt1 = (b - a)//c + 1
else:
    cnt1 = (b - a)//c
if l1 == 0:
    cnt1 += 1

l2 = a % d
r2 = b % d

if l2 > r2:
    cnt2 = (b - a)//d + 1
else:
    cnt2 = (b - a)//d
if l2 == 0:
    cnt2 += 1

e = (c*d)//math.gcd(c,d)
l3 = a % e
r3 = b % e

if l3 > r3:
    cnt3 = (b - a)//e + 1
else:
    cnt3 = (b - a)//e
if l3 == 0:
    cnt3 += 1

print((b - a + 1) - cnt1 - cnt2 + cnt3)

Submission status: Accepted

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

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

def divc(x):
  """ [A, B]にxの倍数がいくつあるかを返す"""
  b = B // x
  r = B % x
  a = A // x
  s = A % x
  res = b - a
  if s == 0:
    res += 1
  return res

ans = B - A + 1 - (divc(C) + divc(D) - divc(lcm(C, D)))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
cc, dd, e = c, d, 1
for i in range(2, int(min(cc, dd)**0.5) + 1):
    if cc%i == 0 and dd%i == 0:
        while cc%i == 0 and dd%i == 0:
            cc //= i
            dd //= i
            e *= i
e *= cc*dd
print(b-a+1 - b//c + (a-1)//c - b//d + (a-1)//d + b//e - (a-1)//e)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    a, b, c, d = [int(x) for x in input().split()]
    cd = c * d // gcd(c, d)
    x = ((b // c) - (a + c - 1) // c + 1)
    y = ((b // d) - (a + d - 1) // d + 1)
    z = ((b // cd) - (a + cd - 1) // cd + 1)
    print(b-a+1-(x+y-z))



        

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""



"""

Submission status: Accepted

Solution code:
import math
a, b, c, d=map(int, input().split())
#aとbの間の cの倍数の数
if a%c==0:
  abc=b//c-a//c+1
else:
  abc=b//c-a//c  
  
#aとbの間の dの倍数の数
if a%d==0:
  abd=b//d-a//d+1
else:
  abd=b//d-a//d
#aとbの間の cdの倍数の数
e=(c*d)//math.gcd(c, d)
if a%e==0:
  abcd=b//e-a//e+1
else:
  abcd=b//e-a//e

print(b-a+1-(abc+abd-abcd))

Submission status: Accepted

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

def lcm(m,n):
    return (m*n) // math.gcd(m,n)

if a%c == 0:
    x = a//c
else:
    x = a//c + 1

if a%d == 0:
    y = a//d
else:
    y = a//d + 1

if a%lcm(c,d) == 0:
    z = a//lcm(c,d)
else:
    z = a//lcm(c,d) + 1
    
X = b//c
Y = b//d
Z = b//lcm(c,d)
    
print((b-a+1) - ((X-x+1) + (Y-y+1) - (Z-z+1)))

Submission status: Accepted

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


def gcd(x, y):
    if x > y:
        x, y = y, x
    while y != 0:
        tmp = x % y
        x = y
        y = tmp
    return x
    
A = A - 1
lcm_CD = C * D // gcd(C, D)
cnt_B = B - (B//C + B//D) + (B//lcm_CD)
cnt_A = A - (A//C + A//D) + (A//lcm_CD)

ans = cnt_B - cnt_A
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
A,B,C,D = map(int,input().split())
count1 = 0
count2 = 0
ans1 = B-B//C-B//D+B//((C*D)//math.gcd(C,D))
A = A-1
ans2 = A-A//C-A//D+A//((C*D)//math.gcd(C,D))
print(ans1-ans2)

Submission status: Accepted

Solution code:
import math

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

x=(a-1)//c

y=b//c
z=(a-1)//d
w=b//d

e=(c * d) // math.gcd(c, d)

p=(a-1)//e

q=b//e

print(b-a+1-y+x-w+z+q-p)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 13, 2020 04:11:55 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


import math
from sys import stdin
input = stdin.readline


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

  # divisible by C
  dc = B//C - (A-1)//C

  # divisible by D
  dd = B//D - (A-1)//D

  lcm = C * D // math.gcd(C, D)
  # divisible by (C and D)
  dcd = B//lcm - (A-1)//lcm

  # print(f'B-A+1: {B-A+1}')
  # print(f'dc   : {dc}')
  # print(f'dd   : {dd}')
  # print(f'lcm  : {lcm}')
  # print(f'dcd  : {dcd}')
  print((B-A+1) - dc - dd + dcd)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

def gcd(x,y):
    if x<y:
        x, y = y, x
    r = x%y
    while r!=0:
        x = y
        y = r
        r = x%y
    return y

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

L = lcm(C,D)

lenB = B-(B//C+B//D-B//L)
A-=1
lenA = A-(A//C+A//D-A//L)
print(lenB-lenA)

Submission status: Accepted

Solution code:
import math

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

def lcm(x, y):
	# 最小公倍数
    return (x * y) // math.gcd(x, y)


A,B,C,D=input2()
lenC=B//C
lenD=B//D
lenCD=B//lcm(C,D)

ans=0
ans=B-(lenC+lenD-lenCD)

A-=1
lenC=A//C
lenD=A//D
lenCD=A//lcm(C,D)

ans-=A-(lenC+lenD-lenCD)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a,b,c,d = I()
x = lcm(c,d)

if a == b:
    if a % c != 0 and a % d != 0:
        print(1)
        sys.exit()
    else:
        print(0)
        sys.exit()

aa = a-1+(a-1)//x - (a-1)//c - (a-1)//d
bb = b+b//x - b//c - b//d
ans = bb-aa

print(ans)

Submission status: Accepted

Solution code:
import math

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

ans_lt_b = b - (b // c + b // d - b // lcm_cd)
ans_lt_a = (a - 1) - ((a - 1) // c + (a - 1) // d - (a - 1) // lcm_cd)
print(ans_lt_b - ans_lt_a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    A,B,C,D = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    c1=(A-1)//C
    d1=(A-1)//D
    c2=(B)//C
    d2=(B)//D
    
    lca=C*D//math.gcd(C,D)
    x1=(A-1)//lca
    x2=(B)//lca

    ans=B-A+1-(c2-c1)-(d2-d1)+(x2-x1)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

a -= 1
a_b = c * d // math.gcd(c, d)
#print(a_b)
ans_a = a - (a // c + a // d - a // a_b)
ans_b = b - (b // c + b // d - b // a_b)

print(int(ans_b-ans_a))

Submission status: Accepted

Solution code:
import math
A,B,C,D = map(int, input().split())
ans1 = B-B//C-B//D
g = math.gcd(C, D)
l = C*D//g
ans1 = ans1+B//l
ans2 = A-1-(A-1)//C-(A-1)//D
ans2 = ans2+(A-1)//l
ans = ans1-ans2
print(int(ans))

Submission status: Accepted

Solution code:
import math

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

lcm = c*d // math.gcd(c, d)

dif = b-a+1
div_c = b//c - (a-1)//c
div_d = b//d - (a-1)//d
div_cd = b//lcm - (a-1)//lcm

ans = dif - (div_c + div_d) + div_cd
print(int(ans))

Submission status: Accepted

Solution code:
# -*-coding: utf-8 -*-

import sys
import math

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

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

def main():
    input = sys.stdin.readline
    a, b, c, d = map(int, input().split())
    a_1 = a - 1
    lcm_cd = lcm(c,d)
    
    a_1_c_count =  a_1 // c
    a_1_d_count =  a_1 // d
    a_lcm_count =  a_1 // lcm_cd

    a_1_result = a_1 - (a_1_c_count + a_1_d_count - a_lcm_count)


    b_c_count = b // c
    b_d_count = b // d
    b_lcm_count = b // lcm_cd

    b_result = (b) - (b_c_count + b_d_count - b_lcm_count)

    result = b_result - a_1_result

    print(result)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 最大公約数を求める
ans = 0
tmp1, tmp2 = C, D
while 1:
  if tmp1 % tmp2 == 0:
    ans = tmp2
    break
  else:
    tmp = tmp1 % tmp2
    tmp1 = tmp2
    tmp2 = tmp
ans = int(C*D/ans)
#print(ans)

num1 = B//C
num2 = (A-1)//C
num_C = num1-num2

num1 = B//D
num2 = (A-1)//D
num_D = num1-num2

num1 = B//ans
num2 = (A-1)//ans
num_CD = num1-num2

print(B-A+1-num_C-num_D+num_CD)

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
 
def gcd(x, y):
    if x < y:
        x, y = y, x
    while True:
        if x % y == 0:
            return y
        x, y = y, x%y
 
x = b - a + 1
cx = b // c - (a-1) // c
dx = b // d - (a-1) // d
cdx = b // (c*d // gcd(c, d)) - (a-1) // (c*d // gcd(c, d))
print(x - cx - dx + cdx)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

a,b,c,d = readInts()

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
import math

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    A, B, C, D = mi()
    A -= 1
    CD_lcm = C * D // math.gcd(C, D)
    ans = B - B//C - B//D + B//CD_lcm
    ans -= A - A//C - A//D + A//CD_lcm
    print(ans)
    return

main()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import math
    A, B, C, D = [int(item) for item in input().split()]

    if B//C == 0:
        num_C = 0
    elif B//C >= 1 and A % C == 0:
        num_C = B // C - A //C + 1
    elif B//C >= 1 and A % C != 0: 
        num_C = B // C - A //C
    else:
        num_C = B // C

    if B//D == 0:
        num_D = 0
    elif B//D >= 1 and A % D == 0:
        num_D = B // D - A //D + 1
    elif  B//D >= 1 and A % D != 0:
        num_D = B // D - A //D
    else:
        num_D = B // D

    lcm = C * D // math.gcd(C, D)
    if B//lcm == 0:
        num_CD = 0
    elif B//lcm > 1 and A  % lcm == 0:
        num_CD = B // lcm - A //lcm + 1
    elif B//lcm > 1 and A  % lcm != 0:
        num_CD = B // lcm - A //lcm
    else:
        num_CD = B // lcm

    # print(num_C, num_D, num_CD)
    print(B - A + 1 - (num_C + num_D - num_CD))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

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

al = b-a+1

cnt_c = b//c - (a-1)//c 

cnt_d = b//d - (a-1)//d 

cnt_t = b//lcm(c,d) - (a-1)//lcm(c,d) 

print(al - cnt_c - cnt_d + cnt_t)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[8]:


import math


# In[5]:


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


# In[14]:


ac = (A-1)//C
bc = B//C
ad = (A-1)//D
bd = B//D
a_both = (A-1)//(C*D//math.gcd(C,D))
b_both = B//(C*D//math.gcd(C,D))
print((B-A+1) - (bc-ac) - (bd-ad) + (b_both-a_both))


# In[ ]:

Submission status: Accepted

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

import math
LCM=c * d //math.gcd(c, d)

tmp1=b//c + b//d - b//LCM #1~bまで調べたとき、割り切れる数の個数
tmp2=(a-1)//c + (a-1)//d - (a-1)//LCM #1~a-1まで調べたとき、割り切れる数の個数
tmp=tmp1-tmp2 #a~bまで調べたとき、割り切れる数の個数
ans=(b-a+1)-tmp

print(ans)

Submission status: Accepted

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

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

x = b - a + 1
cx = b // c - (a-1) // c
dx = b // d - (a-1) // d
cdx = b // (c*d // gcd(c, d)) - (a-1) // (c*d // gcd(c, d))

print(x - cx - dx + cdx)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from math import gcd
a, b, c, d = map(int, input().split())


def dev(n):
    return b // n - -(-a // n) + 1

print(dev(1) - dev(c) - dev(d) + dev(c * d//gcd(c,d)))

Submission status: Accepted

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

c = (B//C) - ((A+C-1)//C) + 1
d = (B//D) - ((A+D-1)//D) + 1
lcm = int(C * D / math.gcd(C, D))
m = (B//lcm) - ((A+lcm-1)//lcm) + 1
ans = (B-A+1) - (c+d-m)
print(int(ans))

Submission status: Accepted

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

t = b-a+1
b1 = b//c
b2 = b//d
if a%c==0:
  a1 = a//c - 1
else:
  a1 = a//c
if a%d==0:
  a2 = a//d - 1
else:
  a2 = a//d

lcm = c*d//gcd(c,d)
e1 = b//lcm
if a%(lcm)==0:
  e2 = a//(lcm) - 1
else:
  e2 = a//(lcm)
  
print(t-((b1-a1)+(b2-a2)-(e1-e2)))

Submission status: Accepted

Solution code:
import sys
import math
input = lambda: sys.stdin.readline().rstrip()

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

def main():
    a, b, c, d = map(int, input().split())
    a_cnt, b_cnt = 0, 0
    a -= 1
    a_cnt = a - ((a//c + a//d) - a // lcm(c, d))
    b_cnt = b - ((b//c + b//d) - b // lcm(c, d))
    print(b_cnt - a_cnt)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

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

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

Submission status: Accepted

Solution code:
def resolve():
    import math
    A, B, C, D = [int(i) for i in input().split()]
    A -= 1
    LCMCD = C * D // math.gcd(C, D)
    ans = (B - B // C - B // D + B // LCMCD) - \
          (A - A // C - A // D + A // LCMCD)
    print(ans)


resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def lcm(x, y): # 最小公倍数
    return (x * y) // math.gcd(x, y)


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

lcm_cd = lcm(c, d)

under_b = b - b//c - b//d + b//lcm_cd
over_a = (a-1) - (a-1)//c - (a-1)//d + (a-1)//lcm_cd

print(under_b - over_a)

Submission status: Accepted

Solution code:
import math

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

b = B - ((B // C) + (B // D) - (B // (C*D // math.gcd(C,D)))) 
a = A-1 - (((A-1) // C) + ((A-1) // D) - ((A-1) // (C*D // math.gcd(C,D))))
res = b - a
print(res)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    a,b,c,d = map(int,ipt().split())
    ans = b-a+1
    ans -= b//c-(a-1)//c
    ans -= b//d-(a-1)//d
    g = c*d//math.gcd(c,d)
    ans += b//g-(a-1)//g
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

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

g = math.gcd(c, d)
l = lcm(c, d)

print(b-a+1 - (b//c - (a-1)//c + b//d - (a-1)//d -b//l + (a-1)//l))

Submission status: Accepted

Solution code:
from math import floor, ceil, gcd

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

if a%c == 0: c_m_min = a
else: c_m_min = a + c - a%c
c_m_max = b - b%c
c_cnt = (c_m_max - c_m_min)//c + 1
if c_m_min > b or c_m_max < a : c_cnt = 0

if a%d == 0: d_m_min = a
else: d_m_min = a + d - a%d
d_m_max = b - b%d
d_cnt = (d_m_max - d_m_min)//d + 1
if d_m_min > b or d_m_max < a : d_cnt = 0

cd = c*d//gcd(c,d)
if a%cd == 0: cd_m_min = a
else: cd_m_min = a + cd - a%cd
cd_m_max = b - b%cd
cd_cnt = (cd_m_max - cd_m_min)//cd + 1
if cd_m_min > b or cd_m_max < a : cd_cnt = 0


ans = b - a + 1 - c_cnt - d_cnt + cd_cnt
print(ans)

Submission status: Accepted

Solution code:
from math import gcd as gcd
a, b, c, d = map(int,input().split())
#cでわれるもの
s = gcd(c, d)
p = c * d // s
divide_c = b // c - (a - 1) // c
divide_d = b // d - (a - 1) // d
divide_cd = b // p - (a - 1) // p
print(int(b - a + 1 - divide_c - divide_d + divide_cd))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import statistics
# import numpy as np
# n = int(input())
# n, m, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
#
#  abc = [int(input()) for i in range(5)]
# n = int(input())
# w = list(map(int, input().split()))
A, B, C, D = list(map(int, input().split()))
# a = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# q = int(input())
# a = list(map(int, input().split()))
# b = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
# bc = [list(map(int, input().split())) for i in range(q)]
# print(min(15*n, 100*(n//10+1), 100*(n//10)+15*(n % 10)))


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


# b以下での個数
cb = B//C
db = B//D
cdb = B//(lcm(C, D))
total_b = cb+db-cdb

# a未満での個数
A -= 1
ca = A//C
da = A//D
cda = A//(lcm(C, D))
total_a = ca+da-cda


# print(total_a)
# print(total_b)
t = B-A
s = total_b-total_a
print(t-s)

Submission status: Accepted

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
a-=1
e=lcm(c,d)

ansb=0
ansb += b//c
ansb += b//d
ansb -= b//e



ansa=0
ansa += a//c
ansa += a//d
ansa -= a//e
print((b-a)-(ansb-ansa))

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
import math
c_div = 0
d_div = 0
if a % c == 0:
    c_div = max(0, 1 + ((b - (b % c)) - a) // c )
else:
    c_div = max(0, 1 + ((b - (b % c)) - (a + (c - a % c))) // c )
if a % d == 0:
    d_div = max(0, 1 + ((b - (b % d)) - a) // d )
else:
    d_div = max(0, 1 + ((b - (b % d)) - (a + (d - a % d))) // d )
gcd_input = c * d // math.gcd(c, d)
if a % gcd_input == 0:
    c_d_div = max(0, 1 + ((b - (b % gcd_input)) - a) // gcd_input )
else: 
    c_d_div = max(0, 1 + ((b - (b % gcd_input)) - (a + (gcd_input - a % gcd_input))) // gcd_input )
print(b - a + 1 - d_div - c_div + c_d_div)

Submission status: Accepted

Solution code:
from math import gcd

a, b, c, d = map(int, input().split())
a -= 1
lcm = c * d // gcd(c, d)
cnt_b = b - b // c - b // d + b // lcm
cnt_a = a - a // c - a // d + a // lcm
print(cnt_b - cnt_a)

Submission status: Accepted

Solution code:
from math import gcd
def main():
    a, b, c, d = map(int, input().split())
    ans = b - a + 1
    e = c*d // gcd(c, d)
    x = b//c - (a-1)//c
    y = b//d - (a-1)//d
    z = b//e - (a-1)//e
    print(ans - x - y + z)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
A,B,C,D = (int(x) for x in input().split())
Num = B-A+1
Dup = C*D//math.gcd(C,D)
MinC  = (A+(C-A%C)%C)//C
MinD  = (A+(D-A%D)%D)//D
MinCD = (A+(Dup-A%Dup)%Dup)//Dup
OvrC  = (B+(C-B%C)%C)//C + (B%C==0)
OvrD  = (B+(D-B%D)%D)//D + (B%D==0)
OvrCD = (B+(Dup-B%Dup)%Dup)//Dup + (B%Dup==0)
CDNum = (OvrC-MinC)+(OvrD-MinD)-(OvrCD-MinCD)
print(Num-CDNum)

Submission status: Accepted

Solution code:
import math
a, b, c, d = map(int, input().split())
e = c*d//math.gcd(c,d)
def ko(a,b,c):
  x = b//c-a//c
  if a%c==0:
    x+=1
  return(x)
print(b-a+1-ko(a,b,c)-ko(a,b,d)+ko(a,b,e))

Submission status: Accepted

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

import math
p=math.gcd(c,d)
q=(c*d)//p

ncd=(b//q)-((a-1)//q)
r=nc+nd-ncd
ans=(b-a+1)-r
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import math

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


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


# 実装を行う関数
def resolve(test_def_name=""):
    a, b, c, d = map(int, input().split())

    ans = b - a + 1

    all_cnt = -(b // c + b // d) + b // (lcm(c, d))
    out_cnt = -((a - 1) // c + (a - 1) // d) + (a - 1) // (lcm(c, d))

    print(ans + all_cnt - out_cnt)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 9 2 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """10 40 6 8"""
        output = """23"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """314159265358979323 846264338327950288 419716939 937510582"""
        output = """532105071133627368"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A,B,C,D = list(map(int,input().split()))
if A%C == 0:
    num_C_bai = (B-(B%C) - A)//C + 1
else:
    num_C_bai = ((B-(B%C) - (A-(A%C)+C)))//C + 1
    
if A%D == 0:
    num_D_bai = (B-(B%D) - A)//D + 1
else:
    num_D_bai = ((B-(B%D) - (A-(A%D)+D)))//D + 1

E = lcm(C,D)

if A%E == 0:
    num_E_bai = (B-(B%E) - A)//E + 1
else:
    num_E_bai = ((B-(B%E) - (A-(A%E)+E)))//E + 1

print(B + 1 - A - num_C_bai - num_D_bai + num_E_bai)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import sys
def li(): return map(int,sys.stdin.readline().rstrip().split())
def lf(): return map(float,sys.stdin.readline().rstrip().split())
def ls(): return sys.stdin.readline().rstrip().split()

a, b, c, d = li()
cn = b//c - (a-1)//c
dn = b//d - (a-1)//d
lcm = c*d//math.gcd(c,d)
cdn = b//lcm - (a-1)//lcm
print(b-a+1-cn-dn+cdn)

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)
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-cc-dd+ee+1)

Submission status: Accepted

Solution code:
from fractions import gcd

A, B, C, D = map(int, input().split())
l = C * D // gcd(C, D)
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // l
y = B - B // C - B // D + B // l
print(y - x)

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int,input().split())
lcm=c*d//math.gcd(c,d)
a1,a2,a3=(a-1)//c,(a-1)//d,(a-1)//lcm
b1,b2,b3=b//c,b//d,b//lcm
ans=b-a+1-(b1+b2-b3-a1-a2+a3)
print(ans)

Submission status: Accepted

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

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

x = [(A-1)//C,(A-1)//D,(A-1)//lcm(C,D)]
y = [B // C,B//D,B//lcm(C,D)]

an = (A-1) - (x[0]+x[1]-x[2])
bn =  B - (y[0]+y[1]-y[2])

print(bn-an)

Submission status: Accepted

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

def gcd(a,b):
    x=max(a,b)
    y=min(a,b)
    
    while True:
#         print(x,y)
        y_ = x % y
        if y_ == 0:
            return y
        x = y
        y = y_

def lcm(a,b):
    ans=Decimal(a*b)/Decimal(gcd(a,b))
    return ans.as_integer_ratio()[0]

CD=lcm(C,D)
len_all = B-A+1
len_c = B//C-(A-1)//C
len_d = B//D-(A-1)//D
len_c_and_d = B//CD-(A-1)//CD

ans=len_all-len_c-len_d+len_c_and_d 
print(int(ans))