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:
#@k0gane_p 
a, b, c, d = [int(i) for i in input().split()]
def gcd(x,y):#最大公約数
    while y:
        x,y = y, x%y
    return x
def lcm(x,y):#最小公倍数
    return x*y // gcd (x,y)
def count(A,B,C):#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-1, c, d)
#A以上B以下の整数のうち、CでもDでも割り切れないものの個数
#if(a % c != 0 and a % d != 0):
    #ans += 1#AがCでもDでも割り切れないなら、足す１
print(ans)

Submission status: Accepted

Solution code:
#@k0gane_p 
a, b, c, d = [int(i) for i in input().split()]
def gcd(x,y):#最大公約数
    while y:
        x,y = y, x%y
    return x
def lcm(x,y):#最小公倍数
    return x*y // gcd (x,y)
def count(A,B,C):#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)
#A以上B以下の整数のうち、CでもDでも割り切れないものの個数
if(a % c != 0 and a % d != 0):
    ans += 1#AがCでもDでも割り切れないなら、足す１
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math
a,b,c,d = map(int, input().split())
x1 = (a-1)//c
x2 = b//c
x = x2-x1
y1 = (a-1)//d
y2 = b//d
y = y2-y1
z1 = (a-1)//((c*d)//fractions.gcd(c,d))
z2 = b//((c*d)//fractions.gcd(c,d))
z = z2-z1
print(int((b-a+1)-x-y+z))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import fractions
    a,b,c,d=map(int, input().split())
    def lcm(c,d):
        return c*d//fractions.gcd(c,d)
    e=lcm(c,d)
    ans=(b-a+1)-((b//c-(a-1)//c)+(b//d-(a-1)//d))+(b//e-(a-1)//e)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

#B以下の整数の個数
x = B - (B // C) - (B // D)
#C,Dの最大公約数を求める
l = fractions.gcd(C, D)
#C,Dの最小公倍数を求める
temp = C * D // l 
#C,Dで重複して引いた数を足し合わせる
x += (B // temp)

#同様にA - 1以下の整数のうちの個数も求める
a = A - 1
y = a - (a // C) - (a // D)
y += (a // temp)

ans = x - y
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
A -= 1
# / だと駄目らしいんだが。。。最小公倍数なのになぜ？
L = C*D//gcd(C,D)
a = A - ((A//C)+(A//D)-(A//L))
b = B - ((B//C)+(B//D)-(B//L))
print(int(b - a))

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

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

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

def F(N,C,D):
  x = N
  x -= N//C
  x -= N//D
  lcm = C*D//gcd(C,D)
  x += N//lcm
  return x

answer = F(B,C,D) - F(A-1,C,D)
print(answer)

Submission status: Accepted

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

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

x = c * d // euclid(c, d)

bd = b // d
bc = b // c
bx = b // x
bsum = b - bd - bc + bx

ad = (a - 1) // d
ac = (a - 1) // c
ax = (a - 1) // x
asum = (a - 1) - ad - ac + ax

print(bsum - asum)

Submission status: Accepted

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

# n 以下の数に m の倍数が何個あるかを返す関数
def baisuNum(n,m):
    return n // m

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

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


# B以下　―　(A-1)以下　にCの倍数何個ある
CC = baisuNum(B,C) - baisuNum(A-1,C)
# B以下　―　(A-1)以下　にDの倍数何個ある
DD = baisuNum(B,D) - baisuNum(A-1,D)
# B以下　―　(A-1)以下　にCかつDの最小公倍数の倍数何個ある
LCM = lcm(C,D)
CD = baisuNum(B, LCM) - baisuNum(A-1, LCM)

print(B-A+1-CC-DD+CD)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C, D = MAP()

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(calc(b,c,d) - calc(a-1,c,d))

Submission status: Accepted

Solution code:
import fractions

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

cd = (c * d) // fractions.gcd(c, d)
b_c = b // c
b_d = b // d
b_cd = b // cd
a_c = (a-1) // c
a_d = (a-1) // d
a_cd = (a-1) // cd

ans = b - b_c - b_d + b_cd - (a-1) + a_c + a_d - a_cd

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

cd = (c * d) // fractions.gcd(c, d)
b_c = b // c
b_d = b // d
b_cd = b // cd
a_c = a // c
a_d = a // d
a_cd = a // cd

ans = b - b_c - b_d + b_cd - a + a_c + a_d - a_cd

if a % c != 0 and a % d!= 0:
    ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ABC162C(a,b):#from:https://atcoder.jp/contests/abc162/submissions/11871774
    while b != 0:
        a %= b
        if a == 0:break
        b %= a
    return max(a,b)
    

a,b,c,d=map(int,input().split())
e=c//ABC162C(c,d)*d
print(b-b//c-b//d+b//e-(a-1-(a-1)//c-(a-1)//d+(a-1)//e))

Submission status: Accepted

Solution code:
def countDivBy(d,a,b):
    resB=b//d
    resA=(a-1)//d
    res = resB-resA
    return res

def gcd(c,d):
    if(d>c):
        c,d = d,c
    a,b=c,d
    r=a%b
    while (r>0):      
        a = b
        b = r 
        r = a%b
    return b
  
A = list(map(int, input().split()))
a, b, c, d = A
g = gcd(c,d)
lcm = (c*d) // g
ans = b - a + 1 - countDivBy(c,a,b) - countDivBy(d,a,b) + countDivBy(lcm,a,b)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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


divC = B//C - (A-1)//C
divD = B//D - (A-1)//D
divL = B//lcm - (A-1)//lcm

print((B-A+1) - divC - divD + divL)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
lcm = lambda a, b: a * b // gcd(a, b)
num_of_multi = lambda n: b // n - a // n - bool(a % n) + 1

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

U = B - A + 1
U_c = (B // C) - (A // C) + int(A % C == 0)
U_d = (B // D) - (A // D) + int(A % D == 0)
U_cd = (B // CD) - (A // CD) + int(A % CD == 0)

ans = U - (U_c + U_d - U_cd)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# solution
import io
import fractions

n, m, k, j = map(int, input().split())
n = n-1
data = int(k*j/fractions.gcd(k, j))
result = (m-m//k-m//j+m//data)-(n-n//k-n//j+n//data)
print(result)

Submission status: Accepted

Solution code:
import fractions

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

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

L = lcm(C, D)

b = B - (B // C + B // D - B // L)
a = (A-1) - ((A-1) // C + (A-1) // D - (A-1) // L)

print(b - a)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

L = lcm(C, D)
numB = B - (B // C + B // D - B // L)
numA_1 = (A - 1) - ((A - 1) // C + (A - 1) // D - (A - 1) // L)
print(numB - numA_1)

Submission status: Accepted

Solution code:
import sys

def gcd(a, b): return gcd(b, a % b) if b else abs(a)
def lcm(a, b): return abs(a // gcd(a, b) * b)

a, b, c, d = map(int, sys.stdin.readline().split())

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

def main():
    print(count(b) - count(a-1))
    
if __name__ ==  '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
A,B,C,D=list(map(int,stdin.readline().strip().split()))
C_A=(A-1)//C
C_B=B//C
D_A=(A-1)//D
D_B=B//D
CD=lcm(C,D)
CD_A=(A-1)//(CD)
CD_B=B//(CD)

print((1+B-A)-((C_B-C_A)+((D_B-D_A)-(CD_B-CD_A))))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
if a % c == 0:
    c_times = b//c - a//c + 1
else:
    c_times = b//c - a//c
#print(c_times)
if a % d == 0:
    d_times = b//d - a//d +1
else:
    d_times = b//d - a//d
#print(d_times)
lcm = c*d // gcd(c,d)
if a % lcm == 0:
    lcm_times = b//lcm - a//lcm +1
else:
    lcm_times = b//lcm - a//lcm
#print(lcm_times)
total = (b-a+1) - (c_times + d_times - lcm_times)
print(total)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    # 全体から、Ｃの倍数 + Ｄの倍数 - (CとDの倍数でもあるやつ)をひけええ
    # C と D の最小公倍数　これは　lcmだね ~ c * d // gcd(c,d)かな
    a,b,c,d = readInts()
    # A 以上　B 以下の中　＝ B以下 - (A-1以下)
    # まず最小公倍数を求めよう
    from fractions import gcd
    lcm = ( c // gcd(c,d) ) * d
    #print(lcm)
    # まず B 以下のやつ


    # 答えは C でも　D でも割り切れないやつだからｗｗｗｗｗｗｗ


    B_ = b - (b // c + b // d - b // lcm)
    #print(B_)
    # んで A-1以下のやつ
    A_ = a-1 - ((a-1) // c  + (a-1) // d - (a-1) // lcm) # 足すな　引け
    # んで答え
    print(B_ - A_)
if __name__ == '__main__':
  main()

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)


A = A - 1

ans = B - (B // C) - (B // D) + (B // (lcm(C, D)))
p = (A - (A // C) - (A // D) + (A // (lcm(C, D))))

print(ans - p)

Submission status: Accepted

Solution code:
import math
import fractions
a,b,c,d=map(int,input().split())
base=b-a+1
n_c=b//c-(a+c-1)//c+1
n_d=b//d-(a+d-1)//d+1
cd=c*d//fractions.gcd(c,d)
n_cd=b//cd-(a+cd-1)//cd+1
print(base-n_c-n_d+n_cd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
total_num = b-a+1
# # of x%c==0
c_num = b//c - (a-1)//c
d_num = b//d - (a-1)//d
from fractions import gcd
lcm = c*d//gcd(c,d)
cd_num = b//lcm - (a-1)//lcm
print(total_num-c_num-d_num+cd_num)

Submission status: Accepted

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

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

Submission status: Accepted

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

l = int(fractions.gcd(c,d) * c / fractions.gcd(c,d) * d / fractions.gcd(c,d))
#print(l)
x = b // c - a // c
y = b // d - a // d
z = b // l - a // l
if a % c == 0 or a % d == 0:
    print(int(b-a-(x+y-z)))
else:
    print(int(b-a-(x+y-z))+1)
#print(x,y,z)

Submission status: Accepted

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

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

a_under = a-1

ans = (b - b//c - b//d + b//p) - (a_under - a_under//c - a_under//d + a_under//p)

print(ans)

Submission status: Accepted

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

# cye bolunenler
c_numbers = b//c - (a-1)//c
# dye bolunenler
d_numbers = b//d - (a-1)//d
# ortak bolunenler
gcd_number = c*d // gcd(c, d)
ortak = b//gcd_number - (a-1)//gcd_number
# result
print(b-a+1-(c_numbers+d_numbers-ortak))

Submission status: Accepted

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

# cye bolunenler
c_numbers = b//c - (a-1)//c
# dye bolunenler
d_numbers = b//d - (a-1)//d
# ortak bolunenler
gcd_number = c*d // gcd(c, d)
ortak = b//(gcd_number) - (a-1)//(gcd_number)
# result
print(b-a+1-(c_numbers+d_numbers-ortak))

Submission status: Accepted

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

# # cye bolunenler
# c_numbers = b//c - (a-1)//c
# # dye bolunenler
# d_numbers = b//d - (a-1)//d
# # ortak bolunenler
# gcd_number = c*d // gcd(c, d)
# ortak = b//gcd_number - (a-1)//gcd_number
# # result
# print(b-a+1-(c_numbers+d_numbers-ortak))

cd = gcd(c, d)
cd = c * d // cd
c_able = b // c - (a - 1) // c
d_able = b // d - (a - 1) // d
cd_able = b // (cd) - (a - 1) // (cd)

print(b - a + 1 - (c_able + d_able - cd_able))

Submission status: Accepted

Solution code:
import sys
import fractions
def input(): return sys.stdin.readline().rstrip()
def cunt_multi(a,b,n):
    #区間[c,d]内のnの倍数の個数
    if b%n<=(b-a+1)%n-1:
        return (b-a+1)//n+1
    else:
        return (b-a+1)//n

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

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

if __name__=='__main__':
    main()

Submission status: Accepted

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

cd = gcd(c,d)
cd = c*d //cd
c_able = b//c - (a-1)//c
d_able = b//d - (a-1)//d
cd_able = b//(cd) - (a-1)//(cd)

print(b- a + 1 - (c_able + d_able - cd_able))

Submission status: Accepted

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

Submission status: Accepted

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

ans = b - a + 1
cd = c*d//fractions.gcd(c,d)
tmp = int(b // c) - int((a-1) // c)
tmp2 = int(b // d) - int((a-1) // d)
tmp3 = int(b //cd) - int((a-1) // cd)


print(ans - tmp - tmp2 + tmp3 )

Submission status: Accepted

Solution code:
import fractions

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

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

multiple_C_under_A = (A - 1) // C
multiple_D_under_A = (A - 1) // D
multiple_CD_under_A = (A - 1) // lcm

multiple_C_under_B = B // C
multiple_D_under_B = B // D
multiple_CD_under_B = B // lcm

total = B - A + 1

print(total - (multiple_C_under_B - multiple_C_under_A + multiple_D_under_B - multiple_D_under_A - (
            multiple_CD_under_B - multiple_CD_under_A)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

num1 = B // C - (A-1) // C
num2 = B // D - (A-1) // D
gcdCD = C * D // gcd(C, D)
num3 = B // gcdCD - (A-1) // gcdCD

print(B - A - num1 - num2 + num3 + 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd


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


A, B, C, D = map(int, input().split())
sc = B//C - (A-1)//C
sd = B//D - (A-1)//D
scd = B//lcm(C, D) - (A-1)//lcm(C, D)
#print(B//lcm(C, D), (A-1)//lcm(C, D))
#print(sc, sd, scd, B-A+1)
print(B-A+1 - sc - sd + scd)

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())
all_count = B-A+1
c_count = B//C - (A-1)//C
d_count = B//D - (A-1)//D
cd_count = B//lcm(C,D) - (A-1)//lcm(C,D)
ans = all_count - c_count - d_count + cd_count
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    # ユークリッド互除法により最大公約数を求める。
    if a < b:
        a, b = b, a

    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
a,b,c,d = map(int,input().split())
b_c = b//c
b_d = b//d
a_c = (a-1)//c
a_d = (a-1)//d
b_cd = b//int((c*d)/gcd(c, d))
a_cd = (a-1)//int((c*d)/gcd(c, d))
print((b-a+1)-(b_c+b_d-b_cd-(a_c+a_d-a_cd)))

Submission status: Accepted

Solution code:
import sys

lines = 1
inp = list()

for _ in range(lines):
    inp.append(sys.stdin.readline().strip())


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


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


lst = [int(i) for i in inp[0].split()]

a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]

# cを小さくする
if c > d:
    c, d = d, c

size = b - a + 1

c_size = b // c + (-a // c) + 1
d_size = b // d + (-a // d) + 1
cd_lcm = lcm(c, d)
cd_size = b // cd_lcm + (-a // cd_lcm) + 1

print(size - c_size - d_size + cd_size)

Submission status: Accepted

Solution code:
def sumcnt(a, b, val):
  am=(a-1)//val
  bm=b//val
  return bm-am

a,b,c,d=map(int,input().split())
p=c
q=d
while p%q>=1:
  bk=p%q
  p=q
  q=bk
mc=c//q
md=d//q
m=mc*md*q
summ=sumcnt(a,b,m)
sumc=sumcnt(a,b,c)
sumd=sumcnt(a,b,d)
print((b-a+1)-(sumc+sumd-summ))

Submission status: Accepted

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

c_cnt = b // c  - (a-1) // c
d_cnt = b // d  - (a-1) // d

lcm = c * d // gcd(c, d)
lcm_cnt = b // lcm  - (a-1) // lcm

print((b - a + 1) - (c_cnt + d_cnt - lcm_cnt))

Submission status: Accepted

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

num1 = c
num2 = d
while (num2>0):
  num1,num2 = max(num1,num2),min(num1,num2)
  r = num1%num2
  num1 = num2
  num2 = r
lcm = int(c*d/num1)

n1 = (a-1)//c+(a-1)//d-(a-1)//lcm
n2 = b//c+b//d-b//lcm
n = n2-n1
ans = b-a+1-n
print(int(ans))

Submission status: Accepted

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

big = max(c, d)
small = min(c, d)
lcm = 0
for i in range(1, 10 ** 8):
    surplus = big % small
    if surplus == 0:
        lcm = c * d // small
        break
    
    big = small
    small = surplus
    

c_num = b // c - (a - 1) // c
d_num = b // d - (a - 1) // d
cd_num = b // lcm - (a - 1) // lcm
num = b - a + 1

#print(num, c_num, d_num, cd_num, lcm)
ans = num - (c_num + d_num - cd_num)

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

num_all = b - a + 1
num_c = (b // c) - (a // c)
if a % c == 0:
    num_c += 1
num_d = (b // d) - (a // d)
if a % d == 0:
    num_d += 1
lcm_cd = lcm(c, d)
num_cd = (b // lcm_cd) - (a // lcm_cd)
if a % lcm_cd == 0:
    num_cd += 1

print(num_all - num_c - num_d + num_cd)

Submission status: Accepted

Solution code:
import math
import fractions

A,B,C,D=map(int,input().split())
E=C*D//(fractions.gcd(C,D))
def P(A,B,Q):
	if A%Q==0:
		return B//Q-A//Q+1
	else:
		return B//Q-A//Q
print(B-A+1-(P(A,B,C))-(P(A,B,D))+(P(A,B,E)))

Submission status: Accepted

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


def func(x,y):
    if(x<0):
        assert()
    if(y<=0):
        assert()
    # print(x,y,int(x/y))
    # return int((x/y))
    # print(x,y,x//y)
    return int((x//y))

# print(func(100,10))


lcm = int((C * D) / int(fractions.gcd(C, D)))
print(int( B - func(B, C) - func(B, D) + func(B, lcm) - A + 1 + func(A-1, C) + func(A-1, D) - func(A-1, lcm)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

A,B,C,D=MI()
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

Submission status: Accepted

Solution code:
import fractions
import sys
sys.setrecursionlimit(10**8)


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


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


def solve(v):
    return v - v // c - v // d + v // lcm2(c, d)


print(solve(b) - solve(a-1))

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


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

Submission status: Accepted

Solution code:
import fractions
import math

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

NUM = B-A+1
CD = int((C*D)/fractions.gcd(C,D))

Ac = A
if Ac%C != 0:
  Ac += C-(Ac%C)

if B > Ac:
  DivC = ((B - Ac)//C)+1
elif B == Ac:
  DivC = 1
else:
  DivC = 0


Ad = A
if Ad%D != 0:
  Ad += D-(Ad%D)

if B > Ad:
  DivD = ((B - Ad)//D)+1
elif B == Ad:
  DivD = 1
else:
  DivD = 0

Acd = A
if Acd%CD != 0:
  Acd += CD-(Acd%CD)

if B > Acd:
  DivCD = ((B - Acd)//CD)+1
elif B == Acd:
  DivCD = 1
else:
  DivCD = 0

print(NUM - DivC - DivD + DivCD)

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

Solution code:
from fractions import gcd

def my_count(a, b, num): #区間[a, b]におけるnumの倍数の個数
  return b//num - (a-1)//num

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

Submission status: Accepted

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

import fractions
f=fractions.gcd(C,D)
f2=C*D//f

res = (B//C + B//D) - ((A-1)//C + (A-1)//D) - (B//f2 - (A-1)//f2)

print((B-A+1) - res)

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split())
import fractions
CD=C*D//(fractions.gcd(C,D))
l=[]
for i in [C,D,CD]:
    if A%i==0:
        l.append(B//i-A//i+1)
    else:
        l.append(B//i-A//i)
print(B-A+1-l[0]-l[1]+l[2])

Submission status: Accepted

Solution code:
def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x
  
def cnt(N, C, D):
  return (N // C) + (N // D) - (N // (C * D // gcd(C, D)))

A, B, C, D = map(int, input().split())
cnt_B_A = cnt(B, C, D) - cnt(A-1, C, D)
print(B-A+1-cnt_B_A)

Submission status: Accepted

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

# B
cntB = 0
cntB += B // C
cntB += B // D
cntB -= B // g

cnt = cntB - cntA
cnt = (B - A + 1) - cnt

print(cnt)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

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

A -= 1
l = lcm(C,D)

a = (B + C) // C - (A + C) // C
b = (B + D) // D - (A + D) // D
c = (B + l) // l - (A + l) // l

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

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def PL(L) : print(*L, sep="\n")

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

A, B, C, D = LI()

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

Submission status: Accepted

Solution code:
import math
from decimal import *
getcontext().prec = 50
a,b,c,d = map(int,input().split())

from functools import reduce
def gcd(a,b):
  if a < b:
    a, b = b, a
  while a % b != 0:
    a, b = b, a % b
  return b

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

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

gcd = lcm_list([c,d])

def solve(n):
	start = n * math.ceil(Decimal(a) / Decimal(n))
	end = n * (Decimal(b) // Decimal(n))
	#print(start,end)
	return (end - start) // n + 1

#print(solve(c),solve(d),solve(gcd))
ans = solve(c) + solve(d) - solve(gcd)
#print(ans)
print(b - a - ans + 1)

Submission status: Accepted

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

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x%y == 0:
        return y
    else:
        return gcd(y, x%y)

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

print(muri(b)-muri(a-1))