Problem:


Score : 300 points

Problem Statement

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

Constraints

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

1\leq C,D\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

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

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

Solution code:
import sys

def S(): return sys.stdin.readline().rstrip()

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

from math import gcd

def f(n):  # 1からnまでCでもDでも割り切れない自然数の個数
    return n-n//C-n//D+n//(C*D//gcd(C,D))

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

Submission status: Accepted

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

print(int(x-y))

Submission status: Accepted

Solution code:
from math import gcd


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

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

# A-1以下で、Cの倍数、Dの倍数、lcm(C,D)のそれぞれの個数
x = [(A - 1) // C, (A - 1) // D, (A - 1) // lcm(C, D)]
# B以下で、Cの倍数、Dの倍数、lcm(C,D)のそれぞれの個数
y = [B // C, B // D, B // lcm(C, D)]

# A-1以下で条件を満たす数
an = (A - 1) - (x[0] + x[1] - x[2])

# B以下で条件を満たす数
bn = B - (y[0] + y[1] - y[2])

print(bn - an)

Submission status: Accepted

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

c1 = (B//C)-((A+C-1)//C)+1
c2 = (B//D)-((A+D-1)//D)+1
c3 = (B//E)-((A+E-1)//E)+1
ans = B-A+1-c1-c2+c3

print(ans)

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int, input().split())
def gcd(a,b):
    if(a%b!=0):
        return gcd(b,a%b)
    else:
        return b
def lcm(a,b):
    return a*b//gcd(a,b)

numb = b-(b//c + b//d) + (b//(lcm(c,d)))
numa = (a-1)-((a-1)//c+(a-1)//d) + ((a-1)//lcm(c,d))
print(numb-numa)

Submission status: Accepted

Solution code:
from math import gcd
def lcm(a, b):
    return a*b//gcd(a, b) 

A, B, C, D = map(int,input().split())
As = [(A-1)//C, (A-1)//D, (A-1)//lcm(C,D)]
Bs = [B//C, B//D, B//lcm(C,D)]

aa = (A-1) - (As[0]+As[1]-As[2])
bb = B - (Bs[0]+Bs[1]-Bs[2])

print(bb-aa)

Submission status: Accepted

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

from math import gcd

def calc(a, b, n):
    return b//n - (a//n+bool(a%n))

print(b-a-calc(a,b,c)-calc(a,b,d)+calc(a,b,c*d//gcd(c,d)))

Submission status: Accepted

Solution code:
from math import gcd
def lcm(a, b):
    return a*b//gcd(a,b)

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

nC = B//C - -(-A//C) + 1
nD = B//D - -(-A//D) + 1
nCD = B//lcm(C,D) - -(-A//lcm(C,D)) + 1

print((B-A+1)-(nC+nD-nCD))

Submission status: Accepted

Solution code:
import math

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

def f(n, c, d):
    sum = n
    sum -= n // c
    sum -= n // d
    lcm = c * d // math.gcd(c, d)
    sum += n // lcm
    return sum

ans = f(b, c, d) - f(a-1, c, d)
print(ans)

Submission status: Accepted

Solution code:
import math


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

if C == 1 or D == 1:
    print(0)
    exit()

count_all = B - A + 1
count_c = (B // C) - math.ceil(A / C) + 1
count_d = (B // D) - math.ceil(A / D) + 1
lcm_cd = C * D // math.gcd(C, D)
count_cd = (B // lcm_cd) - math.ceil(A / lcm_cd) + 1

ans = count_all - (count_c + count_d - count_cd)
print(ans)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
from math import *
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:
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)

a,b,c,d = map(int,input().split())
total =b-a+1##総数
cnum= b//c-(a-1)//c##cの倍数
dnum =b//d-(a-1)//d##dの倍数
m = lcm(c,d)
mnum = b//m -(a-1)//m##最小公倍数の倍数

print(total-(cnum+dnum-mnum))

Submission status: Accepted

Solution code:
import math

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

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

def calc(N):
    return N-N//C-N//D+N//lcm(C,D)

print(calc(B)-calc(A-1))

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 = map(int,input().split())
a -= 1
A = a-((a//c) + (a//d) - a//lcm(c,d))
B = b-((b//c) + (b//d) - b//lcm(c,d))
print(B-A)

Submission status: Accepted

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

t = c*d//gcd(c,d)
x = (a-1) - ((a-1)//c + (a-1)//d) + (a-1)//t
y = b - (b//c + b//d) + b//t

print(y-x)

Submission status: Accepted

Solution code:
# coding: utf-8
import math
a, b, c, d = map(int,input().split())

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

ans = b//c-(a-1)//c#cで
ans += b//d-(a-1)//d#dで
#print(ans)

ans -= b//e-(a-1)//e#両方で
print(int(b-a+1-ans))

Submission status: Accepted

Solution code:
import math

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


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

CL=(A-1)//C
CH=B//C
DL=(A-1)//D
DH=B//D
ACD=(A-1)//lcm(C,D)
BCD=B//lcm(C,D)

#print(CL,CH,DL,DH,ACD,BCD)

ans=(B-A+1)-((CH-CL)+(DH-DL)-(BCD-ACD))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

A,B,C,D=map(int,input().split())
BA=B-A
CD=lcm(C,D)
AC=A%C
AD=A%D
ACD=A%CD
ans=BA+1

ans-=max((BA-(C-AC)%C)//C,0)
ans-=max((BA-(D-AD)%D)//D,0)
ans+=max((BA-(CD-ACD)%CD)//CD,0)


if (BA-(C-AC)%C)>=0:
    ans-=1

if (BA-(D-AD)%D)>=0:
    ans-=1

if (BA-(CD-ACD)%CD)>=0:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

a, b, c, d = map(int, input().split())
cd = (c * d) // gcd(c, d)
aa = (a - 1) - (((a - 1) // c) + ((a - 1) // d) - ((a - 1) // cd))
bb = b - ((b // c) + (b // d) - (b // cd))
print(bb - aa)

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
import numpy as np
cmin = (a - 1) // c + 1
cmax = b // c
dmin = (a - 1) // d + 1
dmax = b // d
lcmcd = np.lcm(c, d)
cdmin = (a - 1) // lcmcd + 1
cdmax = b // lcmcd
csum = cmax - cmin + 1
dsum = dmax - dmin + 1
cdsum = cdmax - cdmin + 1
print((b - a + 1) - (csum + dsum - cdsum))

Submission status: Accepted

Solution code:
from math import *
a,b,c,d = map(int,input().split())
f =(c*d)//gcd(c,d)
r = f
rock = 2
compteur= (b//f)-(a//f)
if a%f==0:
  compteur +=1
div1 = ((b//c)-(a//c))
div2 = ((b//d)-(a//d))
if  a%c == 0:
  div1+=1
if a%d ==0:
  div2 +=1
roger =(div1+div2)-compteur
mm = (b-a)+1
print(mm-roger)

Submission status: Accepted

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

import math

bc = b//c
bd = b//d
bcd = b//(c*d//math.gcd(c,d))

ac = (a-1)//c
ad = (a-1)//d
acd = (a-1)//(c*d//math.gcd(c,d))

ans = (b-bc-bd+bcd)-((a-1)-ac-ad+acd)

print(ans)

Submission status: Accepted

Solution code:
import math

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

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

x = b//c-a//c 

x += b//d-a//d

x -= b//e-a//e 

if a%c == 0:
    x += 1
    
if a%d == 0:
    x += 1
    
if a%e == 0:
    x -= 1
    
print(b-a-x+1)

Submission status: Accepted

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

from math import*
upto_B=B-(B//C+B//D-B//(C*D//gcd(C,D)))
upto_A=A-1-((A-1)//C+(A-1)//D-(A-1)//(C*D//gcd(C,D)))

print(upto_B-upto_A*(A>2))

Submission status: Accepted

Solution code:
import math

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

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

q11 = (a-1)//c
q12 = (a-1)//d

q21 = b//c
q22 = b//d

q3 = (a-1)//lcm(c,d)
q4 = b//lcm(c,d)
print(b-(a-1) - (q21-q11) - (q22-q12) + (q4-q3))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def lcm(a,b):
    ori_a=a
    ori_b=b
    while b!=0:
        a,b=b,a%b
    return (ori_a*ori_b)//a

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


b_div=b//lcm(c,d)
bc=b//c
bd=b//d
a=a-1
a_div=a//lcm(c,d)

ac=a//c
ad=a//d
print((b-bc-bd+b_div)-(a-ac-ad+a_div))

Submission status: Accepted

Solution code:
import math

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

a -= 1

x = a // c
y = a // d
z = a // lcm

ans1 = a - (x + y - z)

x = b // c
y = b // d
z = b // lcm

ans2 = b - (x + y - z)

print(ans2 - ans1)

Submission status: Accepted

Solution code:
import math


A, B, C, D = [int(_) for _ in input().split()]
X = C * D // math.gcd(C, D)
# print(X)


def f(n):
    c = n // C
    d = n // D
    x = n // X
    res = n - c - d + x
    # print(f"{n}, {c}, {d}, {x} = {res}")
    return res


ans = f(B) - f(A) + 1
if A % C == 0 or A % D == 0:
    ans -= 1

print(ans)

Submission status: Accepted

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

s1 = (a-1) // c
s2 = (a-1) // d
s3 = (a-1) // (c*d//math.gcd(c,d))
S = (a-1) - (s1 + s2 -s3)

l1 = b // c
l2 = b // d
l3 = b // (c*d//math.gcd(c,d))
L = b - (l1 + l2 - l3)

print(L-S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split())
a=B//C-(A-1)//C
b=B//D-(A-1)//D
def lcm(x,y):
    return x*y//gcd(x,y)

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

z=lcm(C,D)
c=B//z-(A-1)//z
print(B-A+1-a-b+c)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print(b-a+1-f(b, c, d)+f(a-1, c, d))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

a,b,c,d = map(int,input().split())
z = lcm(c,d)
ac = a // c *c
if a % c > 0:
    ac += c
ad = a // d * d
if a % d > 0:
    ad += d
az = a // z * z
if a % z > 0:
    az += z
bc = b // c * c
bd = b // d * d
bz = b // z * z
uc = (bc - ac) // c
ud = (bd - ad) // d
uz = (bz - az) // z
print((b-a)-(uc+ud)+uz)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
cc = b//c -(a-1)//c
dd = b//d -(a-1)//d
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)
cd = lcm(c, d)
cdcd = b//cd -(a-1)//cd
print(b-a+1-cc-dd+cdcd)

Submission status: Accepted

Solution code:
import sys
from math import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    L = C // gcd(C, D) * D
    c1, c2 = (A + C - 1) // C, B // C
    d1, d2 = (A + D - 1) // D, B // D
    l1, l2 = (A + L - 1) // L, B // L

    ans = (B - A + 1) - ((c2 - c1 + 1) + (d2 - d1 + 1) - (l2 - l1 + 1))
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    G = C // gcd(C, D) * D
    c1, c2 = (A + C - 1) // C, B // C
    d1, d2 = (A + D - 1) // D, B // D
    g1, g2 = (A + G - 1) // G, B // G

    ans = (B - A + 1) - ((c2 - c1 + 1) + (d2 - d1 + 1) - (g2 - g1 + 1))
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
from decimal import Decimal as dec 
a, b, c, d = map(dec,input().split())
if a % c ==0:
    c_explicit = b // c - a // c + 1
else:
    c_explicit = b // c - a // c 
if a % d ==0:
    d_explicit = b // d - a // d + 1
else:
    d_explicit = b // d - a // d 
e = gcd(int(c), int(d))
e = dec(e)
gcl = (c / e) * (d / e) * e
if a % gcl ==0:
    e_explicit = b // gcl - a // gcl + 1
else:
    e_explicit = b // gcl - a // gcl 
g = b - a + 1 - c_explicit - d_explicit + e_explicit
print(g)

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
# 対象となる数の個数
num = B - A + 1
# Cで割り切れる数の個数
C_div = B // C - (A - 1) // C
# Dで割り切れる数の個数
D_div = B // D - (A - 1) // D
# CでもDでも割り切れる数の個数
CandD =  (C * D) // math.gcd(C, D)
CandD_div = B // CandD - (A - 1) // CandD
# CもしくはDで割り切れる数の個数
CorD_div = C_div + D_div - CandD_div
res = num - CorD_div
print(res)

Submission status: Accepted

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


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

n=(b//c)-((a-1)//c)
m=(b//d)-((a-1)//d)
o=(b//e)-((a-1)//e)



print(b-a+1-n-m+o)

Submission status: Accepted

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

def num_fact_in(begin, end):
    def f(div):
        return end//div - (begin-1)//div
    return f

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

f = num_fact_in(a, b)
print(b - a + 1 - (f(c) + f(d) - f(lcm)))

Submission status: Accepted

Solution code:
import math

def lec(a, b):
    # aとbの最小公倍数
    return a * b // math.gcd(a, b)

def cal_num(a, b, x):
    # a ~ bの数値の中にxの倍数が入っている数
    if b >= x:
        x_cum = b // x - (a-1) // x
    else:
        x_cum = 0
    return x_cum

if __name__ == "__main__":
    A, B, C, D = map(int, input().split())

    CD = lec(C, D)
    C_num = cal_num(A, B, C)
    D_num = cal_num(A, B, D)
    CD_num = cal_num(A, B, CD)
    answer = B - A + 1 - C_num - D_num + CD_num

    print(answer)

Submission status: Accepted

Solution code:
#n=int(input())
a,b,c,d=map(int,input().split())
#t=int(input())
#al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
import math

lcm=(c//math.gcd(c,d))*d #最小公倍数

cnum=b//c-(a-1)//c
dnum=b//d-(a-1)//d
cdnum=b//lcm-(a-1)//lcm

ans=b-a+1-(cnum+dnum)+cdnum
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

#from math import gcd
from fractions import gcd

f = gcd(c,d)
f2 = c*d//f

rem_ans = b//c - (a-1)//c + b//d - (a-1)//d - (b//f2 - (a-1)//f2)
ans = b-a+1-rem_ans
print(ans)

Submission status: Accepted

Solution code:
def maxcount(x,y):#x以下の整数でyで割り切れる数
    return x//y
def mincount(x,y):#x未満の整数でyで割り切れる数
    if x%y==0:
        return x//y -1
    else:
        return x//y
from fractions import gcd
a,b,c,d=map(int,input().split())
#全体-(cで割り切れる or dで割り切れる)
tot = b-a+1

div_c = maxcount(b,c)-mincount(a,c)
#print(div_c)
div_d = maxcount(b,d)-mincount(a,d)
#print(div_d)
GCD=gcd(c,d)
lcm=(c*d)//GCD
#print(lcm)

div_both = maxcount(b,lcm)-mincount(a,lcm)
#print(div_both)
ans=tot-(div_c+div_d-div_both)
print(ans)

Submission status: Accepted

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

cc=b//c-a//c
dd=b//d-a//d
lcm=c*d//fractions.gcd(c,d)
#print(lcm)
ee=b//lcm-a//lcm
if a%c==0:
  cc+=1
if a%d==0:
  dd+=1
if a%lcm==0:
  ee+=1
print(allab-cc-dd+ee)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def euclid(a, b):
  if b == 0:
    return a
  else:
    return euclid(b, a%b)
a, b, c, d=map(int,input().split())
if a%c==0:
  ac = a//c
else:
  ac = (a//c)+1
bc=b//c
n=bc-ac+1
if a%d == 0:
  ad = a//d
else:
  ad = (a//d)+1
bd = b//d
m = bd-ad+1
new = (c*d)//euclid(c, d)
if a%(c*d)==0:
  cnew=a//new
else:
  cnew=(a//new)+1
dnew=(b//new)
r=dnew-cnew+1
s=n+m-r
print(b-a+1-s)

Submission status: Accepted

Solution code:
def euclid(a, b):
  if b == 0:
    return a
  else:
    return euclid(b, a%b)
A,B,C,D=map(int,input().split())
if A%C==0:
  k=A//C
else:
  k=(A//C)+1
if B%C==0:
  t=B//C
else:
  t=(B//C)
n=t-k+1
if A%D==0:
  a=A//D
else:
  a=(A//D)+1
b=B//D
m=b-a+1
mi=(C*D)//euclid(C, D)
if A%(C*D)==0:
  c=A//mi
else:
  c=(A//mi)+1
d=(B//mi)
r=d-c+1
s=n+m-r
print(B-A+1-s)

Submission status: Accepted

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

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)


def solve(a, b, c, d):
    lcm_c_and_d = lcm(c, d)
    a -= 1
    p = a - a//c - a//d + a//lcm_c_and_d
    q = b - b//c - b//d + b//lcm_c_and_d

    return q-p


if __name__ == '__main__':
    a, b, c, d = map(int, input().split())

    print(solve(a, b, c, d))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d=map(int,input().split())
e=c*d//gcd(c,d)#最小公倍数
sm=(b//c-(a-1)//c)+(b//d-(a-1)//d)-(b//e-(a-1)//e)
print(int(b-a+1-sm))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int, input().split())
def f(x):
  p = b//x
  q = a//x
  if a%x == 0:
    return(p-q+1)
  else:
    return(p-q)
  
k = f(c)+f(d)-f((c*d)//gcd(c,d))
print(b-a+1-k)

Submission status: Accepted

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

import fractions
cd = c * d // fractions.gcd(c,d)
z = b//(cd) - -(-a//(cd)) + 1

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x
a,b,c,d=map(int,input().split())
total=b-a+1
f1=(b//c)-(a//c)
if a%c==0:
    f1+=1
f2=(b//d)-(a//d)
if a%d==0:
    f2+=1
gcd=gcd(c,d)
lcm=(c*d)//gcd
f3=(b//lcm)-(a//lcm)
if a%lcm==0:
    f3+=1
f=f1+f2-f3
print(total-f)

Submission status: Accepted

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

from fractions import gcd


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

C_ = B // C
D_ = B // D

C_a = (A-1) // C
D_a = (A-1) // D

# 最小公倍数
CD = (C * D) // gcd(C, D)    # C*D / (最大公約数)

CD_ = (B // CD)
CD_a = ((A-1) // CD)

ans = B - (A-1) - (C_ - C_a) - (D_ - D_a) + (CD_ - CD_a)

print(int(ans))

Submission status: Accepted

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

#c,d,lcm(c,d)の倍数がa~bの区間にいくつあるか調べる関数
def check(p):
    if a%p==0:
        e = a//p
    else:
        e = (a//p) +1

    if b%p==0:
        f = b//p
    else:
        f = (b//p)
        
    return(f-e+1)
        

lcm = (c*d)//gcd(c,d)
    
ans = b-a+1 -(check(c)+check(d)) +check(lcm)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    A, B, C, D = map(int, input().split())
    d = D
    c = C
    gcd = 0
    while gcd == 0:
        if d % c == 0:
            gcd = c
        else:
            e = d%c
            d = c
            c = e
    lcm = C*D//gcd
    A = A-1
    print((B-B//C-B//D+B//lcm)-(A-A//C-A//D+A//lcm))
resolve()

Submission status: Accepted

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

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

x = ((a-1)//c)+((a-1)//d)-((a-1)//lcm)
y = (b//c)+(b//d)-(b//lcm)

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

Submission status: Accepted

Solution code:
import math
 
A, B, C, D = list(map(int,input().split()))
 
def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)
 
def lcm_(x,y):
    return (x * y) // gcd_(x, y)
 
def f(x):
    if A % x:
        a = A + (x - A % x)
    else:
        a = A
    if B - a >= 0:
        temp = (B - a + 1) // x
        if (B - a + 1) % x:
            return temp + 1
        return temp
    else:
        return 0
    
ans = (B - A + 1) - f(C) - f(D) + f(lcm_(C, D))
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

def lcm_(x,y):
    return (x * y) // gcd_(x, y)

def f(x, y):
    return x // y

lcm = lcm_(C, D)
ret1 = A - 1 - f(A - 1, C) - f(A - 1, D) + f(A - 1, lcm)
ret2 = B - f(B, C) - f(B, D) + f(B, lcm)
ans = ret2 - ret1
print(ans)

Submission status: Accepted

Solution code:
#from math import gcd
from fractions import gcd

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

# step 1
aa = a // c
if (a % c == 0):
    aa -= 1
bb = b // c
ans = bb - aa

# step 2
aa = a // d
if (a % d == 0):
    aa -= 1
bb = b // d
ans += bb - aa

'''
Python3.5
>>
最大公約数
import math
z = math.gcd(a,b)
最小公倍数
z = (a * b)//math.gcd(a,b)

Python3.4
from fractions import gcd
'''
# step 3
z = (c * d) // gcd(c, d)

aa = a // z
if (a % z == 0):
    aa -= 1
bb = b // z
ans -= bb - aa

tar = b - a + 1 - ans
print(tar)

Submission status: Accepted

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

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

print(B-A+1-((B//C+B//D-B//(num(C, D)))-((A-1)//C+(A-1)//D-(A-1)//(num(C, D)))))

Submission status: Accepted

Solution code:
from fractions import gcd

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

# 最小公倍数
lcm = (C * D) // gcd(C, D)

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

print(count)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
AdivC = (a-1)//c
BdivC = b//c
AdivD = (a-1)//d
BdivD = b//d
gc = fractions.gcd(c,d)
div = (c*d)//gc
AdivCandD = (a-1)//div
BdivCandD = b//div

divC = BdivC - AdivC
divD = BdivD - AdivD
divCandD = BdivCandD - AdivCandD
ans = b-a+1
ans = ans -(divC+divD-divCandD)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int, input().split())
def f(p):
  if a % p ==0:
    return(b//p - a//p + 1)
  else:
    return(b//p - a//p)
  
print(b-a+1 - (f(c)+f(d) - f(int(c*d/gcd(c,d)))))

Submission status: Accepted

Solution code:
import fractions

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

# cで割り切れる、またはdで割り切れるものから、両方で割り切れるものを引く

# cで割り切れる; i
i = b//c - (a-1)//c

# dで割り切れる; j
j = b//d - (a-1)//d

#両方で割り切れる; k
lcm = c*d // (fractions.gcd(c,d))
k = b//lcm - (a-1)//lcm

print(int((b-a+1)-i-j+k))

Submission status: Accepted

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

Submission status: Accepted

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

def gcd(a,b):
    if b>a:
        a,b = b,a
    while b:
        a,b = b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)
E = lcm(C,D)

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

print(R)

Submission status: Accepted

Solution code:

[A,B,C,D] = list(map(int,input().split()))
#print(C,D)
#both
import fractions
f=fractions.gcd(C,D)
f2=C*D//f
#print(f2)

both=B//f2 - (A-1)//f2
#print('both', both)

#C
Ccount=B//C - (A-1)//C
#print('C', Ccount)

#D
Dcount=B//D - (A-1)//D
#print('D', Dcount)

print(B-A+1 -(Ccount+Dcount-both))

Submission status: Accepted

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

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

a -= 1
ans = ans - (b//c) - (b//d) + (b//(lcm(c,d)))
ans = ans + (a//c) + (a//d) - (a//(lcm(c,d)))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def main():
    a, b, c, d = map(int, input().split())
    c_num = (b//c-(a-1)//c)
    d_num = (b//d-(a-1)//d)
    cd_num = (b//lcm(c, d)-(a-1)//lcm(c, d))
    ans = b-a+1-c_num-d_num+cd_num
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

x=b-a+1
A=a-1
bclcm=(d*c)//fractions.gcd(c,d)
y=(b//c)+(b//d)-(b//(bclcm))
z=(A//c)+(A//d)-(A//(bclcm))

ans=x-y+z

print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
 
def main():
    a,b,c,d = map(int,input().split(" "))
    n = b - a + 1
    cdiv = b//c - (a-1)//c
    ddiv = b//d - (a-1)//d
    cddiv = b//(c * d // gcd(c, d))  - (a-1)//(c * d // gcd(c, d))
    print(n - cdiv -ddiv + cddiv)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

def get_num(X):
    num_c = X // C
    num_d = X // D
    common = X // lcm
    return X - (num_c + num_d) + common


print(get_num(B) - get_num(A - 1))

Submission status: Accepted

Solution code:
def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)

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

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

sb1 = b // c
sb2 = b // d
sb3 = b // lcm(c,d)

b2 = b - sb1 - sb2 + sb3

sa1 = a // c
sa2 = a // d
sa3 = a // lcm(c,d)

a2 = a - sa1 - sa2 + sa3

print(b2-a2)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

tmp = B // C + B // D - A//C - A // D
if A%C == 0:
    tmp += 1
if A%D == 0:
    tmp += 1
lcm = lcm_base(C, D)
tmp -= (B//lcm - A//lcm)
if A%lcm == 0:
    tmp -= 1
print(B-A+1-tmp)

Submission status: Accepted

Solution code:
import sys

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return c // b

def solve():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    divC = B // C - (A - 1) // C
    divD = B // D - (A - 1) // D
    cd = lcm(C, D)
    divCD = B // cd - (A - 1) // cd
    print(B - A + 1 - (divC + divD - divCD))


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC131C - Anti-Division
from fractions import gcd

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

Submission status: Accepted

Solution code:
def main():
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)
    def lcd(a, b):
        return int(a / gcd(a, b)) * b
    
    a, b, c, d = map(int, input().split())

    def anti_div(x, y, z):
        # x:n以下の対象の値, y:割る値1, z:割る値2
        # 全体からcで割れるものを引くそして、dで割れるものを引く c,dどちらでも割れるものをたす
        cnt = x
        cnt -= x // c
        cnt -= x // d
        # cでもdでも割れるものがいくつあるか
        cnt += x // lcd(c, d)
        return cnt
    # a以上b以下でどうこうっていう時の数え上げは
    # b以下で数えて「a-1以下」で数えたのを引く
    ans = anti_div(b, c, d) - anti_div(a-1, c, d)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    A, B, C, D = map(int, input().split())
    num_C_div = B // C - (A - 1) // C
    num_D_div = B // D - (A - 1) // D
    CD_lcm = lcm(C, D)
    num_CandD_div = B // (CD_lcm) - (A - 1) // (CD_lcm)
    num_CorD_div = num_C_div + num_D_div - num_CandD_div
    print((B - A + 1) - num_CorD_div)


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def count_div(N, C, D):

    t = N // C + N // D - N // (C * D // fractions.gcd(C, D))
    return N - t


def solve():

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

from fractions import gcd
lcm = c * d // gcd(c, d)
# lcm = int(c * d / gcd(c, d)) #lcm値が微妙に異なるがこちらでも通る？
#print(lcm)

a_num = (a-1)//c + (a-1)//d - (a-1)//lcm
b_num = (b)//c + (b)//d - (b)//lcm

print(b-a+1 - (b_num - a_num))

Submission status: Accepted

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

from fractions import gcd
lcm = c * d // gcd(c, d)
#lcm = int(c * d / gcd(c, d))

a_num = (a-1)//c + (a-1)//d - (a-1)//lcm
b_num = (b)//c + (b)//d - (b)//lcm

print(b-a+1 - (b_num - a_num))

Submission status: Accepted

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

from fractions import gcd
#lcm = c * d // gcd(c, d)
lcm = int(c * d / gcd(c, d))

a_num = (a-1)//c + (a-1)//d - (a-1)//lcm
b_num = (b)//c + (b)//d - (b)//lcm

print(b-a+1 - (b_num - a_num))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions


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



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

    sss = b//c - (a-1)//c
    ssss = b//d - (a-1)//d
    di = lcm(c,d)
    sssss = b // di - (a - 1) // di if di != 0 else 0
    print((b-a+1) - (sss+ssss-sssss))


if __name__ == '__main__':
    main2()

Submission status: Accepted

Solution code:
import math
import fractions

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

Cans = (B // C  + (-A // C)) + 1
Dans = (B // D  + (-A // D)) + 1

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

CDans = (B // CDlcm  + (-A // CDlcm)) + 1

ans = (B - A + 1) - (Cans + Dans - CDans)
print(ans)

Submission status: Accepted

Solution code:
import fractions

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


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


ans=B -(B//C+B//D-B//kobaisu)

ans2=(A-1)-((A-1)//C +(A-1)//D - (A-1)//kobaisu)

print(int(ans-ans2))