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(a, b):
    if a < b:
        a, b = b, a
    return b if a%b == 0 else gcd(b, a%b)

def solve(a, b, c, d):
    ans = b - a + 1
    for p in [c, d]:
        ans -= b // p - (a-1) // p
    for p in [c*d//gcd(c,d)]:
        ans += b // p - (a-1) // p
    return ans

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

Submission status: Accepted

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

pd=(b//p-(a-1)//p)
qd=(b//q-(a-1)//q)

c = p*q//fractions.gcd(p,q)
cd=(b//c-(a-1)//c)

ans= (b-a+1)-(pd+qd-cd)

print(ans)

Submission status: Accepted

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

A = (a-1)//c + (a-1)//d - (a-1)//(lcm(c,d))
B = b//c + b//d - b//(lcm(c,d))
print(U - B + A)

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

c_count = b // c - (a-1) // c
d_count = b // d - (a-1) // d
cd_lcm = lcm(c, d)
cd_count = b // cd_lcm - (a-1) // cd_lcm

ans = 1 + b - a - (c_count + d_count - cd_count)
print(ans)

Submission status: Accepted

Solution code:
import fractions
def lcm(C,D):
    return C*D//fractions.gcd(C,D)
A,B,C,D = map(int, input().split())
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:
from fractions import*
a,b,c,d=map(int,input().split())
f=lambda x:x-x//c-x//d+x//(c*d//gcd(c,d))
print(f(b)-f(a-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())
a-=1
ac = a//c
ad = a//d
bc = b//c
bd = b//d
cd = lcm(c,d)

if cd <= b:
	print((b-a)-((bc+bd)-(ac+ad))+(b//cd-a//cd))
else:
	print((b-a)-((bc+bd)-(ac+ad)))

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

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

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

a, b, c, d = readmi()
t1 = b // c - (a - 1) // c
t2 = b // d - (a - 1) // d
l = lcm(c, d)
t3 = 0
t3 = b // l - (a - 1) // l
k = t1 + t2 - t3
print(b - a + 1 - k)

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

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

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

a, b, c, d = readmi()
t1 = b // c - (a - 1) // c
t2 = b // d - (a - 1) // d
l = lcm(c, d)
t3 = 0
t3 = b // l - (a - 1) // l
k = t1 + t2 - t3
print(b - (a - 1) - k)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
import sys

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


A,B,C,D = map(int,input().split())
if C == 1 or D == 1:
    print(0)
    sys.exit(0)

E = lcm(C,D)
c = (A-1)//C + 1 if C!=1 else A
d = (A-1)//D + 1 if D!=1 else A
e = (A-1)//E + 1 if E!=1 else A
cde = [[c,C], [d,D], [e,E]]
cnt_cde = []
for x,y in cde:
    if x*y < B:
        cnt_cde.append((B-x*y)//y+1)
    elif x*y == B:
        cnt_cde.append(1)
    else :
        cnt_cde.append(0)
answer = B-A+1-(cnt_cde[0]+cnt_cde[1]-cnt_cde[2])
print(answer)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())
Cdiv = B // C - (A - 1) // C
Ddiv = B // D - (A - 1) // D
gcd_CD = int(C * D / fractions.gcd(C, D))
CDdiv = B // gcd_CD - (A - 1) // gcd_CD
result = int(B - (A - 1) - Cdiv - Ddiv + CDdiv)
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def Euclidean(x,y):
    if y == 0:
        return x
    else:
        return Euclidean(y,x%y)

A,B,C,D = [int(x) for x in input().split()]
count = B - A + 1
E = Euclidean(C,D)
F = int(C*D/E)

C_ = B//C - (A-1)//C
D_ = B//D - (A-1)//D
C_and_D = B//F - (A-1)//F
print(count - (C_ + D_ - C_and_D))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int, input().split())
c_n = b//c - (a-1)//c
d_n = b//d - (a-1)//d
l = (c*d)//gcd(c,d)
l_n = b//l - (a-1)//l
print(b - a - c_n - d_n + l_n + 1)

Submission status: Accepted

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

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

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

l = lcm(C, D)

A = A-1
N_range = B - A
l_sum = (B//l) - (A//l)
c_sum = (B//C) - (A//C)
d_sum = (B//D) - (A//D)
print(N_range - c_sum - d_sum + l_sum)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def baisu(x,a):
    return int(x//a)
a,b,c,d = map(int,input().split())

to_a = a-1 - baisu(a-1,c) - baisu(a-1,d) + baisu(a-1,int(c*d/gcd(c,d)))
to_b = b - baisu(b,c) - baisu(b,d) + baisu(b,int(c*d/gcd(c,d)))

print(to_b - to_a)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def baisu(x,a):
    return int(x//a)
a,b,c,d = map(int,input().split())

to_a = a-1 - baisu(a-1,c) - baisu(a-1,d) + baisu(a-1,c*d//gcd(c,d))
to_b = b - baisu(b,c) - baisu(b,d) + baisu(b,c*d//gcd(c,d))

print(to_b - to_a)

Submission status: Accepted

Solution code:
import fractions


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


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


if __name__ == "__main__":
    a, b, c, d = map(int, input().split())
    a -= 1
    cnt = b - a
    cnt -= b//c - a//c
    cnt -= b//d - a//d
    l = lcm(c, d)
    cnt += b//l - a//l
    print(cnt)

Submission status: Accepted

Solution code:
from fractions import gcd
def solve(L, R, A, B):
  return query(R, A, B) - query(L-1, A, B)
def query(N, A, B):  # num 1..N not div by A nor B
  return N - N/A - N/B + N/(A*B /gcd(A,B))
print solve(*map(int, raw_input().split()))

Submission status: Accepted

Solution code:
s = input().split()
s = list(map(int,s))
A = s[0]
B = s[1]
C = s[2]
D = s[3]
if A%C > 0:
  i = B//C - A//C
else:
  i = B//C - A//C + 1
if A%D > 0:
  j = B//D - A//D
else:
  j = B//D - A//D + 1
from fractions import gcd
p = (C*D)//(gcd(C,D))
if A%p > 0:
  k = B//p - A//p
else:
  k = B//p - A//p + 1
print(B-A+1-(i + j - k))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(m,n):
    i = max(m,n)
    j = min(m,n)
    return sgcd(i,j)

def sgcd(i,j):
    if j == 0:
        return i
    else:
        return sgcd(j,i%j)

l = list(map(int,input().split()))
A = l[0]
B = l[1]
C = l[2]
D = l[3]

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

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

Submission status: Accepted

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

A, B,C,D = map(int, input().split())
 
b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
print((B-(A-1))-(b_num-a_num))

Submission status: Accepted

Solution code:
from fractions import gcd 

l = list(map(int,input().split()))
A = l[0]
B = l[1]
C = l[2]
D = l[3]

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

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

Submission status: Accepted

Solution code:
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Bad")
    elif q == 0:print("Good")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

#n = ip()                                     #入力整数1つ
a,b,c,d= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
if a == b:
    if a%c and a%d:
        print(1)
    else:print(0)
elif min(a,b)+1 == max(a,b):
    s =0
    if a%c and a%d:s+=1
    if b%c and b%d:s+=1
    print(s)
else:
    sub1 = (b)//d - (a-1)//d
    sub2 = (b)//c - (a-1)//c
    inter = lcm(c,d)
    sub3 = (b)//inter - (a-1)//inter
    print(b-a-sub1-sub2+sub3+1)

Submission status: Accepted

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

#条件を満たすB以下の整数の個数と条件を満たすA-１以下の整数の個数を求める
#b以下のcとdの倍数を求める
cmulb = round(b // c)
dmulb = round(b // d)
#a-1以下のcとdの倍数を求める(b以下に存在する割れる数の個数)
cmula = round((a-1) // c)
dmula = round((a-1) // d)

#重複を求める
#cとdの最大公約数を求める
#ユークリッドの互除法を使う
surplus = 1
re = max(c,d)
do = min(c,d)
while surplus > 0:
    surplus = re % do
    re = do
    do = surplus
g = re
#cとdの最小公倍数を求める
i = round(c * d / g)
#B以下の重複を求める
dupb = round(b // i)
#A-1以下の重複を求める
dupa = round((a - 1) // i)

#B以下の条件を満たす整数の数
corrb = b - cmulb - dmulb + dupb
#A-1以下の条件を満たす整数の数
corra = a - 1 - cmula - dmula + dupa

print(corrb - corra)

Submission status: Accepted

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

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

a = int(B//C) - int((A-1)//C)
b = int(B//D) - int((A-1)//D)
c = int(B//lcm(C,D)) - int((A-1)//lcm(C, D))

count = B - (A - 1) - (a + b - c)
print(count)

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

#Cの倍数
if A % C ==0:
    C_start = A // C
else:
    C_start = (A//C)+1

C_end = B//C
C_count =-C_start+C_end+1

#Dの倍数
if A % D ==0:
    D_start = A // D
else:
    D_start = (A//D)+1

D_end = B//D
D_count =-D_start+D_end+1

#CとDの倍数
CD=C*D//gcd(C, D)
if A % CD ==0:
    CD_start = A // CD
else:
    CD_start = (A//CD)+1

CD_end = B//CD
CD_count =-CD_start+CD_end+1

count = (B-A+1)-(C_count +D_count -CD_count)
print(count)

Submission status: Accepted

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

# aとbの小公倍数を返す関数
def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b) #再帰定義
    
#B以下のCの倍数の個数
div_c = int(B//C)
#B以下のDの倍数の個数
div_d = int(B//D)
#B以下のC,Dの倍数の個数
mygcd = gcd(C, D)#C,Dの最大公約数
l = int((C*D)//mygcd) #C,Dの最少公倍数
div_gcd = int(B//l)
myansB = B - div_c -div_d + div_gcd

#A以下のCの倍数の個数
div_cA = int((A-1)//C)
#B以下のDの倍数の個数
div_dA = int((A-1)//D)
#B以下のC,Dの倍数の個数
div_gcdl = int((A-1)//l)
myansA = A-1 - div_cA - div_dA + div_gcdl

print(myansB-myansA)

Submission status: Accepted

Solution code:
import fractions

def lcm(a, b):
    return a * b // fractions.gcd(a, b)
    
def f(x, a, b):
    return x - x // a - x // b + x // lcm(a, b)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(x, y):  #最大公約数を求める
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義


if __name__ == "__main__":
    a, b, c, d =  map(int, input().split())
    
    
    
    bai_c = int(b // c)
    bai_d = int(b // d)

    l  = int((c * d) / gcd(c, d))
    b_duplicated = int(b // l)

    bai_c2 = int((a - 1) // c)
    bai_d2 = int((a - 1) // d)
    
    l2 = int((c * d) / gcd(c, d))
    a_duplicated = int((a - 1) // l2)
    
    ans = (b - (bai_c + bai_d - b_duplicated)) - ((a - 1) - (bai_c2 + bai_d2 - a_duplicated))
    print(int(ans))

Submission status: Accepted

Solution code:
import fractions

def cnt(a, b, c):
    cnt = b // c - (a - 1) // c
    return cnt

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

Submission status: Accepted

Solution code:
import fractions

def cnt(a, b, c):
    cnt = b // c - (a - 1) // c
    return cnt

def main():
    a, b, c, d = map(int, input().split())
    lcm = c * d // fractions.gcd(c, d)
    c, d, lcm = cnt(a, b, c), cnt(a, b, d), cnt(a, b, lcm)
    print(b - a + 1 - c - d + lcm)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions

# A以上B以下の数でXの倍数の個数
def countX(X) :
    if X > B :
        return 0

    minX = (A - 1) // X
    maxX = B // X

    return maxX - minX

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

ans = B - A + 1

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

ans -= countX(C)
ans -= countX(D)
ans += countX(Z)

print(int(ans))

Submission status: Accepted

Solution code:
import fractions

def Lcm(a,b):
    return a*b//fractions.gcd(a,b)
def Kosu(min,max,k):
    if(min%k==0):
        tyousei=1
    return max//k-(min-1)//k

min,max,a,b=map(int,input().split())
c=Lcm(a,b)
print(max+1-min-Kosu(min,max,a)-Kosu(min,max,b)+Kosu(min,max,c))

Submission status: Accepted

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

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

lcm=C*D//gcd(C,D)
con1=B//C - (A-1)//C
con2=B//D - (A-1)//D
con3=B//lcm - (A-1)//lcm

print(B-(A-1)-(con1+con2-con3))

Submission status: Accepted

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

if c == 1 or d == 1:
    print(0)
    exit()

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

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

e = lcm(c, d)

bCount = b // c + b // d - b // lcm(c, d)
aCount = (a - 1) // c + (a - 1) // d - (a - 1) // lcm(c, d)

print(b - a - (bCount - aCount) + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
import time
import re
import math
import fractions

def main():
    A,B,C,D=map(int,input().split())
    ccount=B//C-(A-1)//C
    dcount=B//D-(A-1)//D
    CD=C*D//fractions.gcd(C,D)
    cdcount=B//CD-(A-1)//CD
    N=B-A+1
    print(N-(ccount+dcount-(cdcount)))
start=time.time()
main()
#print("処理速度 {}sec".format(time.time()-start))
#"YNeos"[True::2]
#A=list(map(int,input().split()))
#A,B,C=map(int,input().split())
#n=int(input())
# global n,A,s,memo,mx,mn,L,B

Submission status: Accepted

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

Submission status: Accepted

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

print(b - a - (nc + nd - ne))

Submission status: Accepted

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

import math

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

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

def myfunc(x, div1, div2):
    div3 = lcm(div1, div2)
    return x-x//div1-x//div2+x//div3

print(myfunc(B, C, D)-myfunc(A-1, C, D))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    if x < y:
        tmp = y
        y = x
        x = tmp
    while y != 0:
        x = x % y
        temp = y
        y = x
        x = temp
    return int(x)

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

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

x = lcm(c, d)

A = a-1 - (a - 1) // c - (a - 1) // d + (a - 1) // x
B = b - b // c - b // d + b // x

print(int(B - A))

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
def gcd(a, b):
  if a % b is 0:
    return b
  return gcd(b, a % b)

def solve(n):
  return n - (n // C) - (n // D) + (n // (C * D // gcd(C, D)))

print(solve(B) - solve(A - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C
def gcd(a,b):
    if a<b: a,b = b,a
    r = a % b
    while(r!=0):
        a,b = b,r
        r = a%b
    return b

def nonDivided(n,s,t):
    if not n > 0:
        return 0
    else:
        lcm = int(s/gcd(s,t)*t)
        return n-n//s-n//t+n//lcm

if __name__=='__main__':
    A,B,C,D = map(int,input().split())
    print(nonDivided(B,C,D)-nonDivided(A-1,C,D))

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    c=x%y
    return gcd(y,c)   
def lcm( x, y):
    return (x*y)//gcd(x,y)
a,b,c,d=map(int,input().split())
C =b//c-(-(-a//c))
D= b//d-(-(-a//d))
EX=  lcm(c,d)
EX=b//EX+(-a//EX)
print(b-a-(C+D)+EX)

Submission status: Accepted

Solution code:
import fractions
import numpy as np
import os
import sys

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

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

A0=A//C
B0=B//C
if(A%C==0):
    B0+=1
C0=B0-A0


A1=A//D
B1=B//D
if(A%D==0):
    B1+=1
D1=B1-A1

A2=A//E
B2=B//E
if(A%E==0):
    B2+=1
E2=B2-A2

if(C==1 or D==1):
    print(0)
else:
    print(int((B-A+1)-(C0+D1-E2)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

if A % C == 0:
    cc = B // C - A // C + 1
else:
    cc = B // C - A // C
if A % D == 0:
    dd = B // D - A // D + 1
else:
    dd = B // D - A // D

E = int(C * D / gcd(C, D))
if A % E == 0:
    cd = B // E - A // E + 1
else:
    cd = B // E - A // E
print(int((B - A + 1) - cc - dd + cd))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
# from math import gcd


def solve(A: int, B: int, C: int, D: int):
    ci = B//C - (A-1)//C
    di = B//D - (A-1)//D
    l = C*D // gcd(C,D)
    xi = B//l - (A-1)//l

    # print(ci,di,xi)
    print(B-A+1-ci-di+xi)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


def lcm_list(*numbers):
    return reduce(lcm, numbers)


cbai = 0
dbai = 0
cdbai = 0
if a % c == 0:
    cbai += 1
if a % d == 0:
    dbai += 1
if a % (lcm(c, d)) == 0:
    cdbai += 1
cbai += b//c-a//c
dbai += b//d-a//d
cdbai += b//(lcm(c, d))-a//(lcm(c, d))
print(b-a+1-(cbai+dbai-cdbai))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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


def divided(a, b, target):
    return b // target - (a - 1) // target


all_num = B - A + 1

div_t1 = divided(A, B, C)
div_t2 = divided(A, B, D)
div_extra = divided(A, B, CD_lcm)

print(all_num - div_t1 - div_t2 + div_extra)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
def solve(N):
    ans = N
    ans -= N//C
    ans -= N//D
    ans += N//(C*D//gcd(C, D))
    return ans
print(solve(B) - solve(A-1))

Submission status: Accepted

Solution code:
import fractions

def f(x, c, d):
    lcm_num = c*d // fractions.gcd(c, d)
    return x - x//c - x//d + x//lcm_num

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

Submission status: Accepted

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

def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b
def multiple_num(x, start, end):
    """
        Return the number of multiples of x in a range
        from start to end (includes end).
    """
    if start % x == 0:
        l = start # minimum multiple above start
    else:
        l = start + (x - (start % x))
    if end % x == 0:
        r = end # maximum multiple below end
    else:
        r = end - (end % x)
    if l > r:
        return 0
    else:
        return (r-l) // x + 1

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

Submission status: Accepted

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

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

def solve(n):
	return n - (n // C) - (n // D) + (n // (C * D // gcd(C, D)))

#print(solve(B))
#print(solve(A - 1))
print(solve(B) - solve(A - 1))

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
inputs = sys.stdin.readlines()
a, b, c, d = [int(x) for x in inputs[0].split(' ')]
e = c * d // gcd(c, d) # lcm(c, d)
 
num_b = b - b // c - b // d + b // e
num_a = (a-1) - (a-1) // c - (a-1) // d + (a-1) // e
 
print(num_b - num_a)

Submission status: Accepted

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

cko = b//c - (a-1)//c
dko = b//d - (a-1)//d
eko = b//e - (a-1)//e
print(b-a+1-cko-dko+eko)

Submission status: Accepted

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

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

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

def func(x):
    return x - x//C - x//D + x//lcm

print(func(B) - func(A-1))

Submission status: Accepted

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

i = b//c- (a-1)//c
j = b//d- (a-1)//d

f=fractions.gcd(c,d)
f2= int(c * d / f)
k = b//f2 - (a-1)//f2

pot = i + j - k

print(b-(a-1)-pot)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import time
import re
import math
import fractions
 
def main():
    A,B,C,D=map(int,input().split())
    N=B-A+1
    sc=hoge(A,C)-A+1
    if sc<=N:
        ccount=(N+C-sc)//C
    else:
       ccount=0
 
    sd=hoge(A,D)-A+1
    if sd<=N:
        dcount=(N+D-sd)//D
    else:
       dcount=0
 
    CD=C * D // fractions.gcd(C, D)
    scd=hoge(A,CD)-A+1
    if scd<=N:
        cdcount=(N+CD-scd)//CD
    else:
       cdcount=0
    print(N-(ccount+dcount-cdcount))
 
 
def hoge(a,b):
    if a%b==0:
        return (a//b)*b
    else:
        #print("({} // {} +1)*{} {}".format(a,b,b,(a//b+1)*b))
        return (a//b+1)*b
start=time.time()
main()
#print("処理速度 {}sec".format(time.time()-start))
#"YNeos"[True::2]
#A=list(map(int,input().split()))
#A,B,C=map(int,input().split())
#n=int(input())
# global n,A,s,memo,mx,mn,L,B

Submission status: Accepted

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions

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

if c == 1 or d == 1:
    print(0)
    exit()

c_left = max(0, [a // c - 1, a // c][a % c != 0])
c_right = b // c

d_left = max(0, [a // d - 1, a // d][a % d != 0])
d_right = b // d

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

cd_left = max(0, [a // cdgcd - 1, a // (cdgcd)][a % (cdgcd) != 0])
cd_right = b // (cdgcd)

c_number = c_right - c_left
d_number = d_right - d_left
cd_number = cd_right - cd_left

print(b - a + 1 - (c_number + d_number - cd_number))

Submission status: Accepted

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

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

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

def func(x):
    return x - int(x//C) - int(x//D) + int(x//lcm)

print(func(B) - func(A-1))

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)
 
cd = lcm(c, d)
 
div_c = b // c - (a-1)//c
div_d = b // d - (a-1)//d
div_cd = b // cd - (a-1)//cd
count = b - a + 1 - div_c - div_d + div_cd
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
a, b, c, d = [int(i) for i in input().split()]
c1 = d if c < d else c
d1 = c if c < d else d
while d1 != 0:
    e = d1
    d1 = c1 % d1
    c1 = e
e = int((c * d) / e)
a -= 1
cnt = (b - a) + int(b // e) - int(a // e) - int(b // c) + int(a // c) - int(b // d) + int(a // d)
print(cnt)

Submission status: Accepted

Solution code:
import math
import fractions

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

n = (A-1) // C
# n = math.ceil(A / C) - 1
m = B // C
if m >= n:
  count_div += m - n

l = (A-1) // D
# l = math.ceil(A / D) - 1
k = B // D
if k >= l:
  count_div += k - l

j = (A-1) // E
# j = math.ceil(A / E) - 1
i = B // E
if i >= j:
  count_div -= i - j

print(B - A + 1 - count_div)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D=map(int,input().split())
#CとDのどちらかで割り切れる
#=(Cで割り切れる)+(Dで割り切れる)-(lcm(C,D)で割り切れる)
L=(C*D)//gcd(C,D)
#(i-1)<A/C<=i
#i*C<=B<(i+1)C
i=(B//C)-((A-1)//C)
j=(B//D)-((A-1)//D)
k=(B//L)-((A-1)//L)
print(B-A+1-(i+j-k))

Submission status: Accepted

Solution code:
import fractions
A,B,C,D=map(int,input().split())
listA=range(A)
listB=range(B+1)
listC=range(0,B+1,C)
listAC=range(0,A,C)
listD=range(0,B+1,D)
listAD=range(0,A,D)
listCD=range(0,B+1,C*D//fractions.gcd(C,D))
listACD=range(0,A,C*D//fractions.gcd(C,D))
lenA=len(listA)
lenB=len(listB)
lenC=len(listC)-len(listAC)
lenD=len(listD)-len(listAD)
lenCD=len(listCD)-len(listACD)
ans=lenB-lenA-lenC-lenD+lenCD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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


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


nbc = B - B // C
nbd = B - B // D
nbl = B - B // lcm(C, D)

nac = A - 1 - ((A - 1) // C)
nad = A - 1 - ((A - 1) // D)
nal = A - 1 - ((A - 1) // lcm(C, D))

b = nbc + nbd - nbl
a = nac + nad - nal

print(b - a)

Submission status: Accepted

Solution code:
import fractions

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

a, b, c, d = map(int, input().split())
a -= 1
cd = lcm(c, d)

upper = b - b//c - b//d + b//cd
lower = a - a//c - a//d + a//cd
ans = upper - lower

print(ans)

Submission status: Accepted

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

#a~bでnで割り切れるものの数
def func(a, b, n):
    answer = (int(b/n) - int((a-1)/n))
    return answer

def func_test2(a, b, n):
    answer = (int(b//n) - int((a-1)//n))
    return answer

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

lcm = int((c * d) / fractions.gcd(c, d))

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

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:
from fractions import gcd

A, B, C, D = map(int, input().split())
L = C * D // gcd(C, D)
a = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // L
b = B - B // C - B // D + B // L
print(b - a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import fractions
def lcm(x, y):
    return (x*y) // fractions.gcd(x, y)
def main():
    A,B,C,D = map(int,input().split())
    E = lcm(C,D)
    Cc = B // C
    Dd = B // D
    Ee = B // E
    flo = A-1
    Cf = flo // C
    Df = flo // D
    Ef = flo // E
    All = B-(Cc+Dd-Ee)
    Sub = flo-(Cf+Df-Ef)
    print(int(All - Sub))
if __name__ == '__main__':
    main()