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:
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+C-1)//C)+1
j=(B//D)-((A+D-1)//D)+1
k=(B//L)-((A+L-1)//L)+1
print(B-A+1-(i+j-k))

Submission status: Accepted

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

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

def sums(x):
    S1 = x//c
    S2 = x//d
    S3 = x// (c*d//gcd(c,d))
    return x - S1 - S2 + S3


print(sums(b)-sums(a-1))

Submission status: Accepted

Solution code:
import fractions

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

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


def cnt(b, c, d, kobai):
    bc = b // c
    bd = b // d
    b_kobai = b // kobai

    return b - bc - bd + b_kobai


b_num = cnt(b, c, d, kobai)
a_num = cnt(a - 1, c, d, kobai)

ans = b_num - a_num

print(int(ans))

Submission status: Accepted

Solution code:
def gcd(a,b):
  if( b == 0 ):
    return a
  else:
    return gcd(b, a%b)
def lcm(a,b):
  return a* b // (gcd(a,b))
a, b, c, d = [int(x) for x in input().split()]
g = lcm(c,d)
a1 = b//c - (a-1)//c + b//d  - (a-1)//d - b// g + (a-1)//g
print( b - a + 1 - a1)

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
m = B // C
count_div += m - n

l = (A-1) // D
k = B // D
count_div += k - l

j = (A-1) // E
i = B // E
count_div -= i - j

print(B - A + 1 - count_div)

Submission status: Accepted

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

Submission status: Accepted

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

num = input().split(" ")
a = int(num[0])-1
b = int(num[1])
c = int(num[2])
d = int(num[3])
e = int(c * d / int(gcd(c, d)))
bb = b - (b//c) -(b//d) +(b//e) 
aa = a - (a//c) -(a//d) + (a//e)
print(int(bb-aa))

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)
lenAC=len(listAC)
lenD=len(listD)
lenAD=len(listAD)
lenCD=len(listCD)
lenACD=len(listACD)
ans=lenB-lenA-lenC+lenAC-lenD+lenAD+lenCD-lenACD
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
    
S = input().split()

A = int(S[0])
B = int(S[1])
C = int(S[2])
D = int(S[3])

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

count_B = B - (B // C) - (B // D) + (B // CD)
count_A = A - 1 - ((A - 1) // C) - ((A - 1) // D) + ((A - 1) // CD)

print(count_B - count_A)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A,B,C,D = list(map(int,input().split()))
def gcd(a,b):
    r = divmod(a,b)[1]
    if r == 0:
        return int(b)
    else:
        return gcd(b,r)
l = (C*D) // gcd(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:
# ABC131C - Anti-Division
from fractions import gcd


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import fractions


def input():
    return sys.stdin.readline()[:-1]


def main():
    a, b, c, d = map(int, input().split())
    x = c*d//fractions.gcd(c, d)
    ans = b-a+1
    ans -= (b//c-a//c)
    ans -= (b//d-a//d)
    ans += (b//x-a//x)
    if a % c == 0:
        ans -= 1
    if a % d == 0:
        ans -= 1
    if a % x == 0:
        ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D = map(int,input().split())
C_div = B//C - (A-1)//C
D_div = B//D - (A-1)//D
CD = (C * D) // gcd(C, D)
CD_div = B//CD - (A-1)//CD
print(B-A+1 - C_div - D_div + CD_div)

Submission status: Accepted

Solution code:
import math

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

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

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

C_ = len(range(A//C*C if A%C==0 else (A//C+1)*C,B+1,C))
D_ = len(range(A//D*D if A%D==0 else (A//D+1)*D,B+1,D))
CD = lcm(C,D)
CD_ = len(range(A//CD*CD if A%CD==0 else (A//CD+1)*CD,B+1,CD))

print(B-A+1-C_-D_+CD_)

Submission status: Accepted

Solution code:
import fractions

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

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

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

def count_not_multiple(n):
    return (B - A + 1) - count_multiple(n)

cnm = count_not_multiple
print(cnm(C) + cnm(D) - cnm(lcm(C, D)))

Submission status: Accepted

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

# 1..c
def F(c,x):
    if c<1:return 0
    return c-(c/x)

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
L=lcm(C,D)        
print(F(B,C)-F(A-1,C)+F(B,D)-F(A-1,D) - F(B,L)+F(A-1,L))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

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

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

C_ = len(range(A//C*C if A//C*C==A else (A//C+1)*C,B+1,C))
D_ = len(range(A//D*D if A//D*D==A else (A//D+1)*D,B+1,D))
CD = lcm(C,D)
CD_ = len(range(A//CD*CD if A//CD*CD==A else (A//CD+1)*CD,B+1,CD))

print(B-A+1-C_-D_+CD_)

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 cnt(inp):
  min_ = inp * ((A-1) // inp + 1)
  max_ = inp * (B // inp)
  num = (max_ - min_) // inp + 1
  return(num)

Ccnt = cnt(C)
Dcnt = cnt(D)
lcm = C*D // gcd(C,D)
CDcnt = cnt(lcm)

print((B+1-A)-Ccnt-Dcnt+CDcnt)

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_test(a,b,n):
    return b//n - (a-1)//n

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

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

Submission status: Accepted

Solution code:
def c_anti_division(A, B, C, D):
    from fractions import gcd

    def num_calc(n):
        """1からnまでの、CでもDでも割り切れない整数の数"""
        return n - (n // C + n // D - n * gcd(C, D) // (C * D))
    return num_calc(B) - num_calc(A - 1)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 22 21:34:54 2019

@author: owner
"""
import numpy as np

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

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

# %%
A, B, C, D = list(map(int, input().split()))
    
CD = lcm(C, D) 

n_C = B//C - (A-1)//C
n_D = B//D - (A-1)//D

n_CD = B // CD - (A-1) // CD
    
ans = int()#- n_C - n_D + 
print('{}'.format(B-A+1-(n_C+n_D-n_CD)))

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 cnt(inp):
  min_ = inp * (int((A-1) // inp) + 1)
  max_ = inp * (int((B) // inp))
  num = (max_ - min_) // inp + 1
#  return([min_,max_,int(num)])
  return(int(num))

Ccnt = cnt(C)
Dcnt = cnt(D)
lcm = C*D // gcd(C,D)
CDcnt = cnt(lcm)

# print(Ccnt, Dcnt, CDcnt,(B+1-A)-Ccnt[2]-Dcnt[2]+CDcnt[2])
print((B+1-A)-Ccnt-Dcnt+CDcnt)

Submission status: Accepted

Solution code:
from fractions import gcd
from decimal import Decimal
A, B, C, D = map(Decimal, input().split())
_A = A-1
print(int(B - _A - (B//C - _A//C + B//D - _A//D - B//(C*D/gcd(C, D)) + _A//int(C*D/gcd(C, D)))))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
bc=int(b//c)
if a%c==0:
    ac=int(a//c)-1
else:
    ac=int(a//c)
bd=b//d
if a%d==0:
    ad=int(a//d)-1
else:
    ad=int(a//d)
e=c
f=d
while f:
    e, f = f, int(e % f)
gcd=int(e)
l=int(c*d/gcd)
bl=int(b//l)
if a%l==0:
    al=int(a//l)-1
else:
    al=int(a//l)
s=int(b-a+1)
s2=int(bc-ac+bd-ad-bl+al)
print(s-s2)

Submission status: Accepted

Solution code:
import fractions

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

a = input()
a, b, c, d = [int(i) for i in a.split(" ")]
dc = (b // c) - ((a-1) // c)
dd = (b // d) - ((a-1)  // d)
dcd = (b // lcm(c, d)) - ((a-1) // lcm(c, d))
print((b - a) + 1 - (dc + dd - dcd))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int, input().split())
bcBaisu = b // c
bdBaisu = b // d
acBaisu = (a -1) // c
adBaisu = (a-1) // d
cdlcm =  c * d // fractions.gcd(c, d)
bcdLcm = b // cdlcm
acdLcm = (a-1) // cdlcm

karib = b - (bcBaisu + bdBaisu -bcdLcm)
karia = a - 1 - (acBaisu + adBaisu - acdLcm)

print(int(karib - karia))

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 - 1) // C)
count2 = (B // D - (A - 1) // D)
count3 = (B // CD - (A - 1) // CD)

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

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)

x =(b//c)-(((a-1)//c))
y =(b//d)-(((a-1)//d))
n =lcm(c,d)
xy=(b//n)-(((a-1)//n))

ans = (b-a+1) - (x+y-xy)
print(ans)

Submission status: Accepted

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

A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D
ck = gcd(C,D)
asb = C*D//ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(int(newb-newa))

Submission status: Accepted

Solution code:
import fractions

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

A = ABCD[0]
B = ABCD[1]
C = ABCD[2]
D = ABCD[3]


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


def floor(a, b):
  # return int((a - a%b)/b)
  return a//b
def gcd(a, b):
  while b != 0:
      a, b = b, a % b
  return a
def lcm(a, b):
  return floor((a * b), gcd(a, b))

firstC = floor((A-1),C)
firstD = floor((A-1),D)
firstCD = floor((A-1),lcm(C,D))

# if A%lcm(C,D) ==0 and firstCD > 0:
#     firstCD -= 1

endC = floor(B,C)
endD = floor(B,D)
endCD = floor(B,lcm(C,D))

End = B-endC-firstD + endCD
First = (A-1) - firstC - firstD + firstCD



thereC = endC - firstC
thereD = endD - firstD
thereCD = endCD - firstCD

NoP = thereC+thereD - thereCD

# print(thereC)
# print(thereD)
# print(thereCD)
# print(NoP)
print((B-A+1)-NoP)
# print(End-First)

Submission status: Accepted

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

# c,dの最大公約数
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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

cd = lcm(c,d)

ans=0
# a-1までで割り切れない個数
ans-=(a-1) - ((a-1)//c+(a-1)//d-(a-1)//cd)

# bまでで割り切れない個数
ans+=b-(b//c+b//d-b//cd)

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

A -= 1

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

A_C = A // C
A_D = A // D
A_Z = A // Z

A_num = A - (A_C + A_D - A_Z)

B_C = B // C
B_D = B // D
B_Z = B // Z


B_num = B - (B_C + B_D - B_Z)


print(B_num - A_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())
#aまで
count_c_a = (a-1) // c
count_d_a = (a-1) // d
count_cd_a = (a-1) // lcm(c, d)
#bまで
count_c_b = b // c
count_d_b = b // d
count_cd_b = b // lcm(c, d)

print(b-(a-1) - ((count_c_b+count_d_b-count_c_a-count_d_a) - (count_cd_b-count_cd_a)))

Submission status: Accepted

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

s = input().split(" ");
a = int(s[0]);
b = int(s[1]);
c = int(s[2]);
d = int(s[3]);
num_c = b//c - (a-1)//c;
num_d = b//d - (a-1)//d; 
num_cd = b//lcm(c, d) - (a-1)//lcm(c,d);
print(b - a + 1 -(num_c + num_d - num_cd))

Submission status: Accepted

Solution code:
import fractions

a,b,c,d = map(int,input().split())
tn = b-a+1

cn = (b//c)-(a-1)//c
dn = (b//d)-(a-1)//d
cd = (c*d)//fractions.gcd(c, d)
cdn = (b//cd)-(a-1)//cd

print(tn-cn-dn+cdn)

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

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

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

#b以下でc,dで割り切れない数
b_anti_devide = b - b//c - b//d + b//lcm
#a未満でc,dで割り切れない数
a_anti_devide = (a - 1) - (a - 1)//c - (a - 1)//d + (a - 1)//lcm

print (b_anti_devide - a_anti_devide)

Submission status: Accepted

Solution code:
import math
from fractions import gcd


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


def count(X, C, D):
    nC = X // C
    nD = X // D
    lcm = C * D // gcd(C, D)
    nCD = X // lcm
    return X - (nC + nD - nCD)

def solve(A, B, C, D):
    return count(B, C, D) - count(A-1, C, D)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

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

Submission status: Accepted

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

def euc(a,b):
    x = a*b
    if(a<b):
        t = b
        b = a
        a = t
    
    r = a%b
    while(r!=0):
        a = b
        b = r
        r = a%b
    
    return int(x/b)

w = euc(C,D)
    
nc = B//C-(A-1)//C
nd = B//D-(A-1)//D
ncd = B//w-(A-1)//w

nb = B - B//C - B//D + B//w
na = (A-1) - (A-1)//C - (A-1)//D + (A-1)//w

n = nc + nd - ncd

print(B - A + 1 - n)

Submission status: Accepted

Solution code:
import fractions as math
A,B,C,D = [int(x) for x in input().split()]
cd = C*D//math.gcd(C,D)
num_c = B//C-(A-1)//C
num_d = B//D-(A-1)//D
num_cd = B//cd-(A-1)//cd
print(B-A+1-(num_c+num_d-num_cd))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 22 21:34:54 2019

@author: owner
"""
import numpy as np

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

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

# %%
A, B, C, D = list(map(int, input().split()))
    
CD = lcm(C, D) 

n_C = np.int(np.floor(B/C) - np.floor((A-1)/C))
n_D = np.int(np.floor(B/D) - np.floor((A-1)/D))

n_CD = B // CD - (A-1) // CD #np.floor(B/CD) - np.floor((A-1)/CD)

Cdiv = B // C - (A-1) // C
Ddiv = B // D - (A-1) // D
import fractions
cddiv = (C*D)//fractions.gcd(C,D)
CDdiv = B // (cddiv) - (A-1) // (cddiv)
    
ans = int(B - A + 1 -Cdiv - Ddiv + n_CD)#- n_C - n_D + 
print('{}'.format(ans))

Submission status: Accepted

Solution code:
import fractions

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

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

AtoB =  B - (A-1)

div_C = (B//C) - ((A-1)//C)
div_D = (B//D) - ((A-1)//D)
div_CD = (B//lcm(C,D)) - ((A-1)//lcm(C,D))

print(AtoB - div_C - div_D + div_CD)

Submission status: Accepted

Solution code:
# coding=utf-8

###
### for atcorder program
###

import sys
import math
import array

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

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

    E = mymath.lcm(C,D)

    Ct = 1
    if A == (A//C)*C:
        Ct = 0

    Cd = 1
    #if B == (B//C)*C:
    #   Cd = 0

    Dt = 1
    if A == (A//D)*D:
        Dt = 0

    Dd = 1
    #if B == (B//D)*D:
    #    Dd = 0

    Et = 1
    if A == (A//E)*E:
        Et = 0

    Ed = 1
    #if B == (B//E)*E:
    #   Ed = 0

    Cwa = (B//C+Cd - (A//C+Ct))
    Dwa = (B//D+Dd - (A//D+Dt))
    CDw = (B//E+Ed - (A//E+Et))
    zen = B - A + 1

    print(zen + CDw - Cwa - Dwa)

    #print(zen - len(list(range(A, B+1))))

    #print(list(x*C for x in range(A//C+Ct, B//C+Cd)))
    #print(list(x*D for x in range(A//D+Dt, B//D+Dd)))
    #print(list(x*E for x in range(A//E+Et, B//E+Ed)))
    #print(list(range(A, B+1)))
    #Dlist  = set(x*D for x in range(A//D, B//D+1))
    #ABlist = set(x for x in range(A,B+1))
    
    #print(len(Clist))

    #print(Clist)
    #print(Dlist)
    #print(Clist | Dlist)
    #print(ABlist)

    #anslist = ABlist - Clist

    #print(anslist)

    #count = len(anslist)
 

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
 
a, b, c, d = (int(x) for x in input().split())
def kansu(x,y,z):
    sta = x
    end = y
    if sta%z != 0:
        sta = sta+(z-(sta%z))
    if end%z != 0:
        end = end-(end%z)
    ans = ((end-sta)//z) +1
    return ans
a1 = kansu(a,b,c)
a2 = kansu(a,b,d)
lcm = c*d//(fractions.gcd(c,d))
a3 = kansu(a,b,lcm)
print(b-a-a1-a2+a3+1)

Submission status: Accepted

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

ans=0
gc=int(c*d/gcd(c,d))

if a%c==0:
    ans-=1
if a%d==0:
    ans-=1
if a%gc==0:
    ans+=1

ans+=(b-a+1)-(b//c+b//d-a//c-a//d-b//gc+a//gc)

print(ans)

Submission status: Accepted

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

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

total = b-a+1
totalc = b//c-(a-1)//c
totald = b//d-(a-1)//d
totalcd = b//lcm-(a-1)//lcm
print(total - (totalc + totald - totalcd))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import itertools
from decimal import *

#debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

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

    import math
    ac = math.ceil(Decimal(a) / Decimal(c))
    bc = math.floor(Decimal(b) / Decimal(c))
    nc = bc - ac + 1

    ad = math.ceil(Decimal(a) / Decimal(d))
    bd = math.floor(Decimal(b) / Decimal(d))
    nd = bd - ad + 1

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

    cd = lcm(c, d)
    acd = math.ceil(Decimal(a) / Decimal(cd))
    bcd = math.floor(Decimal(b) / Decimal(cd))
    ncd = bcd - acd + 1

    total = b - a + 1
    dprint(total, ac, bc, nc)
    dprint(total, ac, bc, nd, nc, ncd)
    print(total - nd - nc + ncd)

solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 22 21:34:54 2019

@author: owner
"""
import numpy as np

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

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

# %%
A, B, C, D = list(map(int, input().split()))
    
CD = lcm(C, D) 

n_C = np.int(np.floor(B/C) - np.floor((A-1)/C))
n_D = np.int(np.floor(B/D) - np.floor((A-1)/D))

# n_CD = np.int(np.floor(B/CD) - np.floor((A-1)/CD))

Cdiv = B // C - (A-1) // C
Ddiv = B // D - (A-1) // D
import fractions
cddiv = (C*D)//fractions.gcd(C,D)
CDdiv = B // (cddiv) - (A-1) // (cddiv)
    
ans = B - A + 1 -Cdiv - Ddiv + CDdiv#- n_C - n_D + CDdiv#n_CD
print('{}'.format(ans))

Submission status: Accepted

Solution code:
import math
from fractions import gcd

def number_calc(A,B,x):
    left = A//x
    right = B//x
    res = right-left
    return res

A,B,C,D = map(int,input().split())
A -= 1
ans = B-A
ans -=number_calc(A,B,C)
ans -=number_calc(A,B,D)
lcm = (C*D)//gcd(C,D)
ans +=number_calc(A,B,lcm)

print(ans)

Submission status: Accepted

Solution code:
def floor(a, b):
  # return int((a - a%b)/b)
  return a//b
def gcd(a, b):
  while b != 0:
      a, b = b, a % b
  return a
def lcm(a, b):
  return floor((a * b), gcd(a, b))
input = list(map(int, input().split(' ')))
total_count = input[1] + 1 - input[0]
div_c = floor(input[1], input[2]) - floor(input[0] -1, input[2])
div_d = floor(input[1], input[3]) - floor(input[0] -1, input[3])
div_cd = floor(input[1], lcm(input[2], input[3])) - floor(input[0] -1, lcm(input[2], input[3]))
print(total_count - (div_c + div_d - div_cd))

Submission status: Accepted

Solution code:
def extgcd(a,b,list=[1,0,0,1]):
    x1,y1,x2,y2 = list
    if b != 0:
        f1 = x2;f2 = y2
        x2 = x1 - int(a/b)*x2
        y2 = y1 - int(a/b)*y2
        list = [f1,f2,x2,y2]
        x,y,a = extgcd(b,a%b,list)
    else:
        x,y = list[:2]
        return x,y,a

    return x,y,a

a,b,c,d = map(int, input().split())
minus = (c*d)//(extgcd(c,d)[2])
ans = b//c + b//d - b//minus
res = (a-1)//c + (a-1)//d - (a-1)//minus
ans = ans-res
t = b-a+1
print(t-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())
c_div = B//C - (A-1)//C
d_div = B//D - (A-1)//D
cd_div = B//lcm(C,D) - (A-1)//lcm(C,D)
ans = (B-A+1) - c_div - d_div + cd_div
print(ans)

Submission status: Accepted

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


def get_num(i):
    return b // i - (a-1) // i


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


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


all_num = b - a + 1
c_num = get_num(c)
d_num = get_num(d)
lcm = lcm(c, d)
lcm_num = get_num(lcm)

print(all_num - c_num - d_num + lcm_num)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

ab1 = B // C -  (A-1) // C
ab2 = B // D -  (A-1) // D

lcd = lcm(C,D)

ab3 = B//lcd - (A-1)//lcd

ans = (B-A+1) - (ab1+ab2-ab3)

print(ans)

Submission status: Accepted

Solution code:
import fractions


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


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

if d < c:
    tmp = c
    c = d
    d = tmp

common = lcm(c, d)

div_c = b//c - (a-1)//c
div_d = b//d - (a-1)//d
div_common = b//common - (a-1)//common
print((b - a) + 1 - div_c - div_d + div_common)

Submission status: Accepted

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

def euc(a,b):
    x = a*b
    if(a<b):
        t = b
        b = a
        a = t
    
    r = a%b
    while(r!=0):
        a = b
        b = r
        r = a%b
    
    return int(x/b)

w = euc(C,D)
    
nc = B//C-(A-1)//C
nd = B//D-(A-1)//D
ncd = B//w-(A-1)//w

nb = B - B//C - B//D + B//w
na = (A-1) - (A-1)//C - (A-1)//D + (A-1)//w

n = nc + nd - ncd

print(nb - na)

Submission status: Accepted

Solution code:
from fractions import gcd
def floor(a, b):
  # return int((a - a%b)/b)
  return a//b
# def gcd(a, b):
#   while a % b != 0:
#       a, b = b, a % b
#   return a
def lcm(a, b):
  return floor((a * b), gcd(a, b))
input = list(map(int, input().split(' ')))
total_count = input[1] + 1 - input[0]
div_c = floor(input[1], input[2]) - floor(input[0] -1, input[2])
div_d = floor(input[1], input[3]) - floor(input[0] -1, input[3])
div_cd = floor(input[1], lcm(input[2], input[3])) - floor(input[0] -1, lcm(input[2], input[3]))
print(total_count - (div_c + div_d - div_cd))

Submission status: Accepted

Solution code:
from sys import stdin
from fractions import gcd
A, B, C, D = [int(_) for _ in stdin.readline().rstrip().split()]
def solve(n, c, d):
    lcm_CD = C * D // gcd(C, D)
    return n - n//c - n//d + n//lcm_CD
print(solve(B,C,D)-solve(A-1,C,D))

Submission status: Accepted

Solution code:
import fractions
  
A,B,C,D= map(int,input().split())
 
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
CD=lcm(C, D)
 
dc =  B//C -  (A-1)//C
dd = B//D - (A-1)//D
dcd = B//CD - (A-1)//CD
 
print(B-A+1-dc-dd+dcd)

Submission status: Accepted

Solution code:
import fractions
# input process
inputData = input().split()
A = int(inputData[0])
B = int(inputData[1])
C = int(inputData[2])
D = int(inputData[3])

C_q_num = (B // C) - (A // C)
if (A % C) == 0:
    C_q_num += 1
D_q_num = (B // D) - (A // D)
if (A % D) == 0:
    D_q_num += 1
CD_lcm = (C * D) // fractions.gcd(C, D)
CD_q_num = (B // CD_lcm) - (A // CD_lcm)
if (A % CD_lcm) == 0:
    CD_q_num += 1
print((B - A + 1) - C_q_num - D_q_num + CD_q_num)

Submission status: Accepted

Solution code:
import fractions

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

def calc(n):
    return n-n//c-n//d+n//(c*d//fractions.gcd(c, d))

print(calc(b)-calc(a-1))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
ans = b - a + 1#ok
a -= 1#ok

g = gcd(c,d)
temp = c*d//g

cc = -int(a//c) + int(b//c)
dd = -int(a//d) + int(b//d)
cd = -int(a//temp) + int(b // temp)

print(ans - cc - dd + cd)

Submission status: Accepted

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


def main():
    A, B, C, D = map(int, input().split())
    R = int(C * D / gcd(C, D))

    tmp = B // C - (A-1) // C + B // D - (A-1) // D - B // R + (A-1) // R
    print(B-A+1-tmp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from fractions import gcd


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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

E = C * D // 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:
A, B, C, D = map(int, input().split())


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


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

total += B // C - (A-1) // C


total += B // D - (A-1) // D


total = total - B // E + (A-1) // E

print(B - A + 1 - total)

Submission status: Accepted

Solution code:
# 最初に入れておくとinputが早くなる
#import sys
from fractions import gcd
#input = sys.stdin.readline

a, b, c, d = map(int, input().split())
# warikireru = set()
# for i in range(b//c+1):
#    for j in range(b // d+1):
#        k = c ** i * d ** j
#        if(a <= k <= b):
#            warikireru.add(k)
# print(warikireru)
# print(b-a+1-len(warikireru))

k = int(c * d / gcd(c, d))
x1 = b-b//c-b//d+b//k
a -= 1
x2 = a - a // c - a // d + a // k
print(x1-x2)

Submission status: Accepted

Solution code:
import sys

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


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


def main():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    E = lcm(C, D)

    total = B - A + 1
    mul_c = max(0, B // C) - max(0, (A-1) // C)
    mul_d = max(0, B // D) - max(0, (A-1) // D)
    mul_e = max(0, B // E) - max(0, (A-1) // E)
    return total - (mul_c + mul_d - mul_e)


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

Submission status: Accepted

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

cnt = 0
s = b - a + 1
cd = (c*d) // gcd(c,d)

m1 = int((a-1) // c)
m2 = int(b // c)
cnt += (m2-m1)
#print(cnt)

m1 = int((a-1) // d)
m2 = int(b // d)
cnt += (m2-m1)
#print(cnt)

m1 = int((a-1) // cd)
m2 = int(b // cd)
cnt -= (m2-m1)
#print(cnt)

#print(cnt)
print(s - cnt)

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

Solution code:
import fractions

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

under_a = a -1
cd_gcd = fractions.gcd(c, d)

b_mul = b - (b//c)-(b//d)+(b//(c*d//cd_gcd))
under_a_mul = under_a - (under_a//c)-(under_a//d)+(under_a//(c*d//cd_gcd))

print(int(b_mul-under_a_mul))

Submission status: Accepted

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

C_ = int(B//C) - int((A-1)//C)
D_ = int(B//D) - int((A-1)//D)

E = int(C * D // int(fractions.gcd(C, D)))
E_ = int(B//E) - int((A-1)//E)

ans = B - A + 1 - C_ - D_ + E_
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math

A,B,C,D = map(int,input().split())
CD_lcm = C*D//fractions.gcd(C,D)
B_ans = B - B//C - B//D + B//CD_lcm
A_ans = (A-1) - (A-1)//C - (A-1)//D + (A-1)//CD_lcm
print(B_ans-A_ans)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
cnt = 0
numc = b // c - (a - 1) // c
numd = b // d - (a - 1) // d
com = int(c * d / fractions.gcd(c,d))
numcd = b // com - (a - 1) // com
print(int(b - a + 1 - (numc + numd - numcd)))