Problem:


Score : 300 points

Problem Statement

You are given four integers A, B, C, and D. Find the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

Constraints

1\leq A\leq B\leq 10^{18}

1\leq C,D\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
# A以上B以下で、CでもDでも割れない数をf(x)とすると
# f(x) = f(B) - f(A - 1)
# B以下で割り切れない数から、A未満の数を引く

# Yで割り切れる数は X // Y
bc = B // C
bd = B // D

# CでもDでも割り切れる数は CとDの最小公倍数
import fractions
# 最小公倍数
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

lcmCD = lcm(C, D)
bcd = B // lcmCD

# A - 1以下の割り切れる数
ac = (A - 1) // C
ad = (A - 1) // D

acd = (A - 1) // lcmCD

# f(B) - f(A - 1)
ans = (B - (bc + bd) + bcd) - ((A - 1) - (ac + ad) + acd)
print(ans)

Submission status: Accepted

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

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

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

def count(a, b, c):
    d = a // b
    e = a // c
    f = a // lcm(b, c)
    return a - d - e + f
ans = count(b, c, d) - count(a, c, d)
if(a % c != 0 and a % d != 0):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
	if a < b:
		a,b = b,a
	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())
a3 = b // c - (a-1) // c
b3 = b // d - (a-1) // d
if c < d:
	c,d = d,c
width = b - a + 1
c3 = b//lcm(c,d) - (a-1)//lcm(c,d)
print(int(width - a3 - b3 + c3))

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)

input = input().split(' ')
A = int(input[0])
B = int(input[1])
C = int(input[2])
D = int(input[3])

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(B-A+1-(div_c+div_d-div_cd))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def gcd(a, b):
    """
    最大公約数を求める
    """
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """
    最小公倍数を求める
    """
    return a*b//(gcd(a, b))


def calc_num(n, C, D):
    """
    0~Nまでで、C or Dで割り切れない数の個数
    """

    div_C = n//C
    div_D = n//D
    div_CD = n//(lcm(C, D))
    return n-div_C-div_D+div_CD


def solve():
    A, B, C, D = map(int, input().split())
    return calc_num(B, C, D)-calc_num(A-1, C, D)


print(solve())

Submission status: Accepted

Solution code:
def lcm(a,b):
    ab = a*b
    while b != 0:
        a, b = b, a%b
    return ab //a

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

Submission status: Accepted

Solution code:
def lcm(a, b):
    ab = a * b
    while b != 0:
        a, b = b, a % b
    return ab // a


def s(n, c, d):
    return n - n//c - n//d + n//lcm(c, d)


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

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//C))+1
# print(c_count)

d_count = (B//D)-(-(-A//D))+1
# print(d_count)

cd_lcm = lcm(C, D)
# print(cd_lcm)
cd_count = (B//cd_lcm)-(-(-A//cd_lcm))+1
# print((B//cd_lcm), (-(-A//cd_lcm)))


print(B-A+1 - c_count - d_count + cd_count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#-------------------------------------
def gcd( x, y ):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

a,b,c,d = map(int,input().split())
cd = c*d
bcnt = b-(b//c+b//d-b//(cd//gcd(c,d)))
acnt = 0
if a>1:
        a -= 1
        acnt = a-(a//c+a//d-a//(cd//gcd(c,d)))

print(bcnt-acnt)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
#cnt = 0
#lst = [i for i in range(a,b+1) if i%c!=0 and i%d!=0]
#print(len(lst))

c_d = int(c*d/gcd(c,d))
a -= 1
c2 = (b//c) - (a//c)
d2 = (b//d) - (a//d)
cd = (b//(c_d)) - (a//(c_d))
print(b-a - (c2+d2-cd))
#print(b-a-(b//c+b//d - a//c+a//d  - b//c_d - a//c_d))
"""
a-=1
a2 = a//c + a//d - a//(c*d)
print(b-a-(b//c + b//d - b//(c*d) - a2))
"""
"""
for i in range(a,b+1):
  if i % c != 0 and i % d != 0:
    cnt += 1
print(cnt)
"""

Submission status: Accepted

Solution code:
i  = list(map(int,input().split()))
a = i[0]
b = i[1]
c = i[2]
d = i[3]

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

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

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

Submission status: Accepted

Solution code:
import fractions

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

count = B - A + 1
lcd_of_CD = C * D // fractions.gcd(C, D)

count -= B // C
count += (A - 1) // C
count -= B // D
count += (A - 1) // D
count += B // lcd_of_CD
count -= (A - 1) // lcd_of_CD

print(count)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
cd=int(c*d/(fractions.gcd(c,d)))
#print(cd)
c1=b//c
c2=(a-1)//c
c3=c1-c2
d1=b//d
d2=(a-1)//d
d3=d1-d2
cd1=b//(cd)
cd2=(a-1)//(cd)
cd3=cd1-cd2
print((b-a+1)-(c3+d3-cd3))
#print(str(c3)+" "+str(d3)+" "+str(cd3))

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

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


def gcb(a, b):
    # a, b = max([a, b]), min([a, b])
    return a if b == 0 else gcb(b, a % b)


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


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

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

Submission status: Accepted

Solution code:

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

x = B // C - (A-1)//C
y = B // D - (A-1) //D
import fractions as f
a = C*D // f.gcd(C,D)
z = B //a - (A-1) // a

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

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())
Cdiv = B // C - (A-1) // C
Ddiv = B // D - (A-1) // D
cddiv = (C*D) // gcd(C, D)
CDdiv = B // (cddiv) - (A-1) // cddiv

print( (B-A+1) - Cdiv - Ddiv + CDdiv )

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
lcm = (c * d) // fractions.gcd(c, d)
a_c_d, a_c_m = divmod(a, c)
a_d_d, a_d_m = divmod(a, d)
a_lcm_d, a_lcm_m = divmod(a, lcm)
lt_a = (a_c_d + (-1 if a_c_m == 0 else 0)) + (a_d_d + (-1 if a_d_m == 0 else 0)) - (a_lcm_d + (-1 if a_lcm_m == 0 else 0))
b_c_d, b_c_m = divmod(b, c)
b_d_d, b_d_m = divmod(b, d)
b_lcm_d, b_lcm_m = divmod(b, lcm)
lte_b = b_c_d + b_d_d - b_lcm_d
print((b - a + 1) - (lte_b - lt_a))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc131/tasks/abc131_c

import fractions

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        x, y = y, x % y
    return x
'''
def lcm(a,b):
	return a*b//gcd(a,b)
'''
a,b,c,d = [int(i) for i in input().split()]
'''
C = 0
D = 0
E = 0
'''
'''
for i in range(int(a / max(c,d,lcm(c,d))),b-a):
    print(i)
    if c * i >= a and c * i <= b and C == 0:
        C = c * i
    if d * i >= a and d * i <= b and D == 0:
        D = d * i
    if lcm(c,d) * i >= a and lcm(c,d) * i <= b and E == 0:
        E = lcm(c,d) * i
    if C != 0 and D != 0 and E != 0:
        break
'''
'''
for i in range(int(a / lcm(c,d)) - 1,int(b / lcm(c,d))+2):
    if lcm(c,d) * i >= a and lcm(c,d) * i <= b and E == 0:
        E = lcm(c,d) * i
        break

for i in range(int(a / c) - 1,int(b / c)+2):
    if c * i >= a and c * i <= b and C == 0:
        C = c * i
        break

for i in range(int(a / d) - 1,int(b / d)+2):
    if d * i >= a and d * i <= b and D == 0:
        D = d * i
        break
'''
#print(lcm(c,d))
#print('')
#print(C,D,E)
'''
c2 = int(b / c) - int(C / c)+1
d2 = int(b / d) - int(D / d)+1
e2 = int(b / lcm(c,d)) - int(E / lcm(c,d))+1
'''
'''
if int(b / c) == b/c:
	print('c')
	c2 += 1
if int(b / d) == b/d:
	print('d')
	d2 += 1
if int(b / lcm(c,d)) == b/lcm(c,d):
	print('e')
	e2 += 1
'''
c2 = b // c - (a-1) // c
d2 = b // d - (a-1) // d
lcm = c * d // fractions.gcd(c,d)
e2 = b // lcm - (a-1) // lcm
'''
if a % c == 0:
	#print('c')
	c2 += 1
if a % d == 0:
	#print('d')
	d2 += 1
if a % lcm(c,d) == 0:
	#print('e')
	e2 += 1
'''
'''
if E == 0:
	e2 = 0
if C == 0:
	c2 = 0
if D == 0:
	d2 = 0
'''

#print(b-a+1,c2,d2,e2)
'''
c1 = list(range(C,b+1,c))
d1 = list(range(D,b+1,d))
e1 = list(range(E,b+1,lcm(c,d)))
print(b-a+1,len(c1),len(d1),len(e1))

print(c1,d1,e1)

print(b-a+1-len(c1)-len(d1)+len(e1))
'''
print(int(b-a+1 - c2 - d2 + e2))

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

nrofC = (B // C) - ((A-1) // C)
nrofD = (B // D) - ((A-1) // D)

cdlcm = (C * D) // gcd(D,C)
nrofCD = (B // cdlcm) - ((A-1) // cdlcm)

print((B-(A-1)) - nrofC - nrofD + nrofCD)

Submission status: Accepted

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

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

def div(x,c,d):
    return x - x//c - x//d + x//lcm(c,d)


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

a = div(a-1,c,d)
b = div(b,c,d)
num = b-a

print(num)

Submission status: Accepted

Solution code:
import itertools

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

def output_list(v):
    print(' '.join(str(x) for x in v))

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

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

def main():
    a, b, c, d = input_ints()
    a -= 1
    print(b - a - calc(a, b, c) - calc(a, b, d) + calc(a, b, c * d // gcd(c, d)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

while y != 0:
	x,y =y,x%y
x = (c*d)//x

count1 = b - (b//c + b//d -b//x)
count2 = (a - 1) - ((a-1)//c + (a-1)//d -(a-1)//x) 
print(count1 - count2)

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

def count(x):
    return x - x//c - x//d + x//lcm(c,d)

print(count(b) - count(a-1))

Submission status: Accepted

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

def getLCM(a, b):
    while True:
        r = a % b
        if r == 0:
            b = int(C*D//b)
            return b
        a = b
        b = r

E = 1
if C != D:
    if C > D:
        E = getLCM(C, D)

    elif D > C:
        E = getLCM(D, C)

    c = int(B // C)
    d = int(B // D)
    e = int(B // E)
    ans1 = (B-c-d+e)

    c = int((A-1) // C)
    d = int((A-1) // D)
    e = int((A-1) // E)
    ans2 = ((A-1)-c-d+e)
else:
    c = int(B // C)
    ans1 = (B-c)

    c = int((A-1) // C)
    ans2 = ((A-1)-c)

ans = ans1 - ans2
if ans < 0:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
t = b//c-(a-1)//c
u = b//d-(a-1)//d
def gcd(p,q):
    if p%q != 0:
        return gcd(q,p%q)
    else:
        return q
k = c*d//gcd(c,d)
v = b//k-(a-1)//k
print(b-a+1-t-u+v)

Submission status: Accepted

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

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

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, raw_input().split())

C_cnt=B/C-(A-1)/C
D_cnt=B/D-(A-1)/D
CD_cnt=B/lcm(C,D)-(A-1)/lcm(C,D)

print (B-A+1)-C_cnt-D_cnt+CD_cnt

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def divx(a,b,x):
	return b//x - (a-1)//x
def gcd(a,b):
	if not b:
		return a
	return gcd(b,a%b)

a,b,c,d=[int(x) for x in input().split(' ')]
lcm=(c*d)//gcd(c,d)
# print(divx(a,b,c))
# print(divx(a,b,d))
# print(divx(a,b,lcm))
ans=divx(a,b,c)+divx(a,b,d)-divx(a,b,lcm)
print(b-a+1-ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

figs = b-a + 1
L = (c*d) // gcd(c,d)


Cdiv = b // c - (a-1) //c
Ddiv = b // d - (a-1) //d
CDdiv =  b // L - (a-1) // L

ans = figs - Cdiv - Ddiv + CDdiv

print (ans)

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

lcmn = lcm(C, D)

candivnum = (B//C + B//D - B//lcmn) - ((A-1)//C + (A-1)//D - (A-1)//lcmn)
print(B-A+1-candivnum)

Submission status: Accepted

Solution code:
import fractions

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

def howmany(num, div1, div2):
  tsumugi = num // div1
  matsuri = num // div2
  kaori = num // (div1 * div2 //fractions.gcd(div1, div2))
  mizuki = num - tsumugi - matsuri + kaori
  return mizuki

A = howmany(a - 1, c, d)
B = howmany(b, c, d)

ans = B - A

print(ans)

Submission status: Accepted

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

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

A,B,C,D = map(int,input().split())
E = lcm(max(D,C),min(D,C))
num = B-A+1
tmp1 = (B//C)+(B//D)-((B//E))
tmp2 = ((A-1)//C)+((A-1)//D)-(((A-1)//E))
print(num-tmp1+tmp2)

Submission status: Accepted

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

A =A-1
CD = C * D // gcd(C, D)
num_A_C = A // C
num_A_D = A // D
num_A_CD = A // CD
num_B_C = B // C
num_B_D = B // D
num_B_CD = B // CD

num_B = B - (num_B_C + num_B_D - num_B_CD)
num_A = A - (num_A_C + num_A_D - num_A_CD)
ans = num_B - num_A
print(ans)

Submission status: Accepted

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

def f(x, c, d):
    res = x
    res -= x//c
    res -= x//d
    res += x//lcm(c,d)
    return res

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

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

Submission status: Accepted

Solution code:
import fractions

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

a -= 1

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

b_sum = b - (b // c) - (b // d) + (b // lcm)
a_sum = a - (a // c) - (a // d) + (a // lcm)

print(b_sum - a_sum)

Submission status: Accepted

Solution code:

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


f = [c]
x = 1000000
k = [c, d]

while x != 0:
    x = max(k) % min(k)

    if x != 0:
        f.append(x)
    k.sort()
    k[1] = x
#print(min(f))

cc = (b // c)- ((a - 1) // c)
dd = (b // d)- ((a - 1) // d)
cd =(b // (c * d // min(f)))- ((a - 1) // (c * d // min(f)))
#print(cc,"cc")
#print(dd,"dd")
#print(cd,"cd")

print(int(b - a + 1 - cc - dd + cd))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
e = c*d//gcd(c,d)
s = b-a+1
def count(z,x=a,y=b):
  if x%z == 0 and y%z == 0:
    return y//z-x//z+1
  elif x%z == 0:
    return y//z-x//z+1
  elif y%z == 0:
    return y//z-x//z
  else:
    return y//z-x//z
t = count(c)
u = count(d)
v = count(e)
print(s-t-u+v)

Submission status: Accepted

Solution code:
import fractions as math

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

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

Cu = B//C       #Cの上限
Cd = -(-A//C)   #Cの下限
Du = B//D       #Dの上限
Dd = -(-A//D)   #Dの下限

#Least common multiple
LCMu = B//(lcm(C,D))
LCMd = -(-A//lcm(C,D))


C_num = Cu - Cd + 1
D_num = Du - Dd + 1
LCM_num = LCMu - LCMd + 1

C_D_num = C_num + D_num - LCM_num
A_B_num = B - A  + 1

ans = A_B_num - C_D_num
print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions as fl

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

#全体の個数
all = b - a + 1
#cとdの最小公倍数
e = c * d // fl.gcd(c, d)
# a以下でcまたはdで割れる個数
r1 = (a-1) // c + (a-1) // d - (a-1) // e
# b以下でcまたはdで割れる個数
r2 = b // c + b // d - b // e
ans = all - (r2 - r1)
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def LI(): return list(map(int, sys.stdin.readline().split()))

A,B,C,D = LI()
A -= 1
upper_cnt = B - (B // C + B // D - B //lcm(D,C))
lower_cnt = A - (A // C + A // D - A //lcm(C,D))


print(upper_cnt-lower_cnt)

Submission status: Accepted

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


def f(x, c, d):
    res = x
    res -= x//c
    res -= x//d
    res += x//lcm(c,d)
    return res

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

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

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
 
def wareruzu(x):
    if b < x:
        return 0
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x) # bより小さい最大の値。
    m = end_b - start_a
    return int(m // x) + 1
 
all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) // fractions.gcd(c,d)))

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

countB = b - (b // c) - (b // d) + (b // lcm(c,d))
countA = a - 1 - ((a - 1) // c) - ((a - 1) // d) + ((a - 1) // lcm(c,d))

print(countB - countA)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def f(n, c, d):
    x = n
    x -= n//c
    x -= n//d
    x += n//lcm(c,d)
    return x

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

Submission status: Accepted

Solution code:
from fractions import gcd
inf = input().split()
A = int(inf[0])
B = int(inf[1])
C = int(inf[2])
D = int(inf[3])

num = B-A+1
target = B
X = C*D//gcd(C,D)

total = B//C + B//D - B//X
lim = (A-1)//C + (A-1)//D - (A-1)//X
print(num-total+lim)

Submission status: Accepted

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

## b = qa + r
#b = C
#a = D
#r = C%D
#while r != 0:
#    b = a
#    a = r
#    r = b%a
#gcd = a
gcd = fractions.gcd(C, D)
CDlcm = C*D//gcd

total = B-(A-1)
Cmuls = B//C - (A-1)//C
Dmuls = B//D - (A-1)//D
CDmuls = B//CDlcm - (A-1)//CDlcm
ans = total - Cmuls - Dmuls + CDmuls
print(ans)

Submission status: Accepted

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

# b = qa + r
b = C
a = D
r = C%D
while r != 0:
    b = a
    a = r
    r = b%a
gcd = a
CDlcm = C*D//gcd

total = B-(A-1)
Cmuls = B//C - (A-1)//C
Dmuls = B//D - (A-1)//D
CDmuls = B//CDlcm - (A-1)//CDlcm
ans = total - Cmuls - Dmuls + CDmuls
print(ans)

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
 
def wareruzu(x):
    if b < x:
        return 0
    if b == x:
        return 1
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x) # bより小さい最大の値。
    m = end_b - start_a
    return m // x + 1
 
all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) // fractions.gcd(c,d)))

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
 
def wareruzu(x):
    if b < x:
        return 0
    if b == x:
        return 1
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x) # bより小さい最大の値。
    m = end_b - start_a
    if m < 0:
        return 0
    return int(m // x) + 1
 
all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) // fractions.gcd(c,d)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 23 14:44:36 2019

@author: Enya
"""

X = input()

A = int(X.split()[0])
B = int(X.split()[1])
C = int(X.split()[2])
D = int(X.split()[3])

from fractions import gcd

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



N_1 = (B // C) 
N_11 = (A-1) // C
N_2 = (B // D)
N_22 =((A-1) // D)
N_3 = (B // E)
N_33 = (A-1) // E

a = B - (N_1 + N_2 - N_3)
b= (A-1) - (N_11 + N_22 - N_33)




print(int(a-b))

Submission status: Accepted

Solution code:
import fractions

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

R = (B - A) + 1
R1 = (A - 1) // C + (A - 1) // D - ((A-1) // LCM)
R2 = B // C + B // D - (B // LCM)

RR = R - (R2 - R1)

print(RR)

Submission status: Accepted

Solution code:
def gcd(a,b):
    while b != 0:
        temp = b
        b = a%b
        a = temp
    return a
A,B,C,D = map(int,input().split())
if C >=D:
    lc = int(C*D/gcd(C,D))
else: lc = int(C*D/gcd(D,C))
A = A-1
A_n = A - (A//C + A//D - A//lc)
B_n = B - (B//C + B//D - B//lc)
print(int(B_n-A_n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

lis=list(map(int,input().split()))
gCD=fractions.gcd(lis[2],lis[3])
CD=int((lis[2]*lis[3])/gCD)
lis[0]=lis[0]-1
AC=lis[0]//lis[2]
AD=lis[0]//lis[3]
ACD=lis[0]//CD
BC=lis[1]//lis[2]
BD=lis[1]//lis[3]
BCD=lis[1]//CD
A=lis[0]-AC-AD+ACD
B=lis[1]-BC-BD+BCD
ans=B-A
print(ans)
#print(AC,AD,BC,BD,CD,ACD,BCD)
#print(lis)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(1000000001)

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

def how_many(num):
    ans = B//num-(A-1)//num
    return ans

count -= how_many(C)
count -= how_many(D)
E = C * D // euclid(D, C)
count += how_many(E)

print(count)

Submission status: Accepted

Solution code:
a,b,c,d = (int(i) for i in input().split())
def gcd(x,y):
    if x%y: return gcd(y,x%y)
    else: return y
m,a = c*d//gcd(c,d),a-1
print(b-a-b//c-b//d+b//m+a//c+a//d-a//m)

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(x, y):
  ret = (x*y)//gcd(x,y)
  return ret
  
def f(n, c, d):
  x = n
  x -= n//c
  x -= n//d
  x += n//lcm(c,d)
  return x

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

Submission status: Accepted

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

dividedbyC = B // C - (A-1) // C
dividedbyD = B // D - (A-1) // D


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


mcl = C * D // gcd(C, D)
dividedbyCandD = B // mcl - (A-1) // mcl
ans = B - A + 1 - (dividedbyC + dividedbyD - dividedbyCandD)
print(ans)

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

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

Submission status: Accepted

Solution code:
def main():
	A, B, C, D = map(int, input().split())
	div_c, div_d, div_cd = 0, 0, 0

	def gcd(x, y):
		if x > y:
			x, y = y, x
		if y % x == 0:
			return x
		return gcd(y%x, x)
	div_c = B//C - A//C
	div_d = B//D - A//D
	if A%C==0:
		div_c += 1
	if A%D==0:
		div_d += 1
	cd = C*D//gcd(C, D)
	div_cd = B//cd - A//cd
	if A%cd==0:
		div_cd += 1
	divable = div_c+div_d-div_cd
	total = B-A+1
	print(total-divable)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - Anti-Division
https://atcoder.jp/contests/abc131/tasks/abc131_c

"""
import sys

from fractions import gcd

def solve(A, B, C, D):
    ans = B - A + 1
    div_c = (B // C) - ((A-1) // C)
    div_d = (B // D) - ((A-1) // D)
    lcm_cd = C*D // gcd(C, D)
    div_cd = (B // lcm_cd) - ((A-1) // lcm_cd)
    return ans - div_c - div_d + div_cd


def main(args):
    A, B, C, D = map(int, input().split())
    ans = solve(A, B, C, D)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

c_div=B//C
d_div=B//D
dc_div=B//((C*D)//gcd(C,D))

not_div1 = B-(d_div+c_div-dc_div)

A =A-1
c_div=A//C
d_div=A//D
dc_div=A//((C*D)//gcd(C,D))

not_div2 = A-(d_div+c_div-dc_div)

print(not_div1-not_div2)

Submission status: Accepted

Solution code:
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
# Function to return LCM of two numbers 
def lcm(a,b): 
    return int((a*b) // gcd(a,b)) 

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

x1 = int(A//C)
x2 = int(A//D)
x3 = int(A//lcm(C,D))

y1 = int(B//C)
y2 = int(B//D)
y3 = int(B//lcm(C,D))

result = int(B-y1-y2+y3-(A-x1-x2+x3))
if(A%C!=0 and A%D!=0):
	result+=1
print(result)

Submission status: Accepted

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

if c == 1 or d == 1:
    print(0)
elif a == b:
    if a%c == 0 or a%d == 0:
        print(0)
    else:
        print(1)
else:
    an1 = (b//c)
    an2 = ((a-1)//c)
    an3 = (b//d)
    an4 = ((a-1)//d) 
    gcd = round(c * d / gcd(c, d))
    an5 = (b//gcd)
    an6 = ((a-1)//gcd)
    if c == d:
        an = an1-an2
    else:
        an = an1-an2 + an3-an4 -(an5-an6)
    print((b-a+1)-an)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



def get_gcd(a,b):
  if a>b: a,b=[b,a]
  return b if a==0 else get_gcd(b%a,a)


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


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import math
import fractions
A, B, C, D = map(int, input().split())
g = int(C*D/fractions.gcd(C,D))
N = B - A + 1
E = B - B//C  - B//D + B//g
F = A-1 - (A-1)//C - (A-1)//D + (A-1)//g
print(int(E-F))

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

N = B - A + 1

E = B//C - (A-1)//C
F = B//D - (A-1)//D
G = B//(lcm(D,C)) - (A-1)//(lcm(D,C))

ans = N - (E + F - G)

print(ans)

Submission status: Accepted

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

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

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

def N(x, y):
    """x以下の整数のうちyで割り切れるものの個数"""
    return x // y

def N2(x, y, z):
    """x以下の整数のうちyまたはzで割り切れるものの個数"""
    return N(x, y) + N(x, z) - N(x, lcm(y, z))

n = N2(B, C, D) - N2(A - 1, C, D)
n = B - A + 1 - n
print(n)

Submission status: Accepted

Solution code:

from collections import defaultdict

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)

def main():
    a, b, c, d = map(int, input().split())
    a -= 1
    all_data = a // c + a // d - a // lcm(c, d)
    all_data = a - all_data
    hiku = b // c + b // d - b // lcm(c, d)
    hiku = b - hiku

    print(hiku - all_data)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
 
def gcd(x,y):
   if x % y == 0:
       return y
   return gcd(y, x % y)
 
CD = (c * d) // gcd(c,d)
 
h_b =b - (b // c) - (b // d) + (b // CD)
h_a = (a - 1) - (a - 1) // c - (a - 1) // d + (a - 1) // CD
 
print(h_b - h_a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 23 09:58:34 2019

@author: Yamazaki Kenichi
"""

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

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

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

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

Submission status: Accepted

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

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

lcm = lcm(C, D)

nA = (A-1)//C + (A-1)//D - (A-1)//lcm
nB = B//C + B//D - B//lcm

print(B-A+1-nB+nA)

Submission status: Accepted

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


def gcm(c, d):
    """
    最大公約数を求める
    """
    while d > 0:
        c, d = d, c % d
    return c


def lcm(c, d):
    """
    最小公倍数を求める
    """
    return c*d//gcm(c, d)


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


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

Submission status: Accepted

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

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

CD = (c * d) // gcd(c,d)

h_b =b - (b // c) - (b // d) + (b // CD)
h_a = (a - 1) - (a - 1) // c - (a - 1) // d + (a - 1) // CD

print(h_b - h_a)

Submission status: Accepted

Solution code:

import fractions

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

l = C * D / fractions.gcd(C, D)
l = int(l)

#条件を満たすB以下の整数の個数
Bn = B -  (B//C + B//D - B//l) 

#条件を満たすA-1以下の整数の個数
An = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//l) 

print(Bn-An)

Submission status: Accepted

Solution code:
try :
    from math import gcd
except ImportError :
    from fractions import gcd

def lcs(c,d,g) :
    return (c*d)//g


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

al = B-(A-1)

divisible_c = B//C - (A-1)//C
divisible_d = B//D - (A-1)//D

G = gcd(C,D)
L = lcs(C,D,G)

divisible_c_and_d = B//L - (A-1)//L

ans = al - (divisible_c + divisible_d - divisible_c_and_d)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcs(c,d,g) :
    return (c*d)//g


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

al = B-(A-1)

divisible_c = B//C - (A-1)//C
divisible_d = B//D - (A-1)//D

G = gcd(C,D)
L = lcs(C,D,G)

divisible_c_and_d = B//L - (A-1)//L

ans = al - (divisible_c + divisible_d - divisible_c_and_d)

print(ans)