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
read = sys.stdin.buffer.read # 全読み込み
readline = sys.stdin.buffer.readline # 一行読み込み
readlines = sys.stdin.buffer.readlines # 一行ずつ全読み込み
sys.setrecursionlimit(10**7) # 再帰限界変更（デフォルトは1000）

"""
# 文字列（数値変換も含む）
n = readline().rstrip() # １行に１文字列のみ
lis = readline().rstrip().split() # # １行に複数の文字列

# 数値（文字変換も含む）
n = int(readline().rstrip()) # １行に数値１個のみ
a, b, c = map(int,readline().rstrip().split()) # １行に複数の数値
A = list(map(int,readline().rstrip().split()))  # １行に複数の数値（リスト受け取り）
lis = [readline().rstrip().split() for _ in range(n)] # １行に複数の数値(m個)かつ、n行続く場合（出力は二次元リスト：[['1', '2'], ['4', '5']]）

# dとAの行が交互に並んでいる場合
s = sys.stdin.readlines()
n, k=map(int, s[0].split())
d=[]
A=[]
for i in s[1:2*k:2]:
    d.append(int(i))
for i in s[2:2*k+1:2]:
    A.append(list(map(int, i.split())))
"""

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

import fractions
f = fractions.gcd(c,d) # 最大公約数
f2 = c*d // f # 最小公倍数

# b以下で条件を満たす個数
shou1=b//c
shou2=b//d
shou3=b//f2
num_b=b-(shou1+shou2-shou3)

# a-1以下で条件を満たす個数
shou4=(a-1)//c
shou5=(a-1)//d
shou6=(a-1)//f2
num_a=(a-1)-(shou4+shou5-shou6)

print(num_b-num_a)

Submission status: Accepted

Solution code:
from fractions import gcd  # for python 3.5, use math.gcd


def main():
    A, B, C, D = list(map(int, input().split(' ')))
    gcd_cd = gcd(C, D)
    lcm_cd = C * D // gcd_cd
    A -= 1
    a = A - A // C - A // D + A // lcm_cd
    b = B - B // C - B // D + B // lcm_cd
    print(b - a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions

a,b,c,d=map(int,input().split())
g=(fractions.gcd(c,d))
l=int((c*d)/g)
C=int(b//c)-int((a-1)//c)
D=int(b//d)-int((a-1)//d)
E=int(b//l)-int((a-1)//l)
print(b-a+1-C-D+E)

Submission status: Accepted

Solution code:
import fractions

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

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

Submission status: Accepted

Solution code:
import fractions

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

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

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(x, y):
    return (x * y) // gcd(x, y)

e = lcm(c, d)

x = b - a + 1
y = b // c - (a - 1) // c
z = b // d - (a - 1) // d
w = b // e - (a - 1) // e

print(x - y - z + w)

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())
x=int(b//c)-int((a-1)//c) +int(b//d) -int((a-1)//d) -int(b//lcm(c,d)) + int((a-1)//lcm(c,d))
print(b-a+1-x)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
A,B,C,D=map(int, sys.stdin.readline().split())
C_cnt=B/C-(A-1)/C
D_cnt=B/D-(A-1)/D
CD_gcd=gcd(C,D)
CD_lcm=C/CD_gcd*D/CD_gcd*CD_gcd
CD_lcm_cnt=B/CD_lcm-(A-1)/CD_lcm
print B-(A-1)-C_cnt-D_cnt+CD_lcm_cnt

Submission status: Accepted

Solution code:
import fractions as math

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

#cの培数の数を調べる
num_c = (b//c) - ((a-1)//c)

#dの培数の数を調べる
num_d = (b//d) - ((a-1)//d)

#dの培数の数を調べる
lcm = c*d//(math.gcd(c,d))
num_cd = (b//lcm) - ((a-1)//lcm)

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

b_c = b//c - (a-1)//c
d_c = b//d - (a-1)//d
cd = (c * d) // fractions.gcd(c, d)
cd_c = b//cd - (a-1)//cd

print((b - a + 1) - (b_c + d_c - cd_c))

Submission status: Accepted

Solution code:
import fractions

def main():
    A,B,C,D = map(int, input().split())  
    lc = lcm(C, D)
    Bsum = B - (B//C) - (B//D) + (B//lc)
    A1 = A-1
    Asum = A1 - (A1//C) - (A1//D) + (A1//lc)
    print(Bsum-Asum)
    
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)



if __name__ == '__main__':
    main()

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())
all = b - (b // c + b // d - b // lcm(c, d))
part = (a - 1) - ((a - 1) // c + (a - 1) // d - (a - 1) // lcm(c, d))


print(all - part)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
 
def ceil(a, b):
  return -(-a//b)
 
a, b, c, d = map(int, input().split())
cd_lcm = c*d//gcd(c, d)
c_left, c_right = ceil(a,c), b//c
d_left, d_right = ceil(a,d), b//d
cd_left, cd_right = ceil(a,cd_lcm), b//(cd_lcm)
cv, dv, cdv = c_right - c_left + 1, d_right - d_left + 1, cd_right - cd_left + 1
print((b - a + 1) - (cv + dv - cdv))

Submission status: Accepted

Solution code:
import sys
from math import ceil
from fractions import gcd

a, b, c, d = map(int, input().split())
if c == 1:
  print(0)
  sys.exit()
cd_lcm = c*d//gcd(c, d)
c_left, c_right = ceil(a/c), b//c
d_left, d_right = ceil(a/d), b//d
cd_left, cd_right = ceil(a/cd_lcm), b//(cd_lcm)
cv, dv, cdv = c_right - c_left + 1, d_right - d_left + 1, cd_right - cd_left + 1
print((b - a + 1) - (cv + dv - cdv))

Submission status: Accepted

Solution code:
import fractions
def main():
    A, B, C, D = map(int, input().split())
    num = (B - A + 1)  - (get_num(B, C, D) - get_num(A-1, C, D))
    print(num)

def get_num(x, C, D):
    num_C = x // C
    num_D = x // D
    f = fractions.gcd(C, D)
    f2 = C*D//f
    num_CD = x // f2
    return 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())
#c_d = math.floor(((c*d)//(math.gcd(c,d))))
c_d = (c*d)//(fractions.gcd(c,d))
#print((math.gcd(c,d)))
a_c = (a-1) // c
a_d = (a-1) // d
a_c_d = (a-1) // c_d
a_ans = (a-1) - a_c - a_d + a_c_d
#ans1 = (a_c + a_d - a_c_d)
#print(c_d)
b_c = b // c
b_d = b // d
b_c_d = b // c_d
b_ans = b - b_c - b_d + b_c_d
#ans2 = (b_c + b_d -b_c_d)
#print(ans2)
#print(math.floor((b-a+1)-(ans2-ans1)))
print(math.floor(b_ans-a_ans))

Submission status: Accepted

Solution code:
from fractions import gcd

a, b, c, d = map(int, input().split())
a= a-1
a_c = a // c
b_c = b // c
a_d = a // d
b_d = b // d
e = c*d // gcd(c, d)

print((b - b_c - b_d + b//e) - (a - a_c - a_d + a//e))

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
n1 = b - b // c - b // d + b // lcm(c,d)
n2 = a - a // c - a // d + a // lcm(c,d)


print(n1 - n2)

Submission status: Accepted

Solution code:
import fractions

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

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

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

print(B_count-A_count)

Submission status: Accepted

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

Submission status: Accepted

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

# ==================== gcd   最大公約数
from fractions import gcd
#from math import gcd

a1=a-1
bn=b-(b//c+b//d-b//(c*d//gcd(c,d)))
an=a1-(a1//c+a1//d-a1//(c*d//gcd(c,d)))

print(bn-an)

Submission status: Accepted

Solution code:
from fractions import gcd

lcm = lambda x, y: x*y // gcd(x, y)

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

b_ = b
b_ -= b // c
b_ -= b // d
b_ += b // lcm(c, d)

a -= 1
a_ = a
a_ -= a // c
a_ -= a // d
a_ += a // lcm(c, d)


print(b_ - a_)

Submission status: Accepted

Solution code:
import fractions

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

a, b, c, d = map(int,input().split())
ans = 0
a = a-1
 
x = b - (b//c + b//d - b//lcm(c,d)) #1~bまでの該当する数
y = a - (a//c + a//d - a//lcm(c,d)) #1~a-1までの該当する数
    
print(x-y)

Submission status: Accepted

Solution code:

import fractions
a,b,c,d = map(int,input().split())	
lcm = c * d // fractions.gcd(c, d)
#print(lcm)
def divisor(x):
	
	x_c = x//c
	x_d = x//d
	#print(x_c,x_d)
	x_lcm = x//lcm
	#print(x_c,x_d,x_lcm)
	return x-x_c-x_d+x_lcm
#print(divisor(b),divisor(a))
ans = divisor(b)-divisor(a-1)
print(ans)

Submission status: Accepted

Solution code:
import fractions

A,B,C,D=map(int,input().split())
E=C*D//fractions.gcd(C,D)
C1 = (A-1)//C
D1 = (A-1)//D
E1 = (A-1)//E
C2 = B//C
D2 = B//D
E2 = B//E

#1-Aまでの数からC or Dで割り切れる数の個数
W1 = C1 + D1 - E1

#1-Bまでの数からC or Dで割り切れる数の個数
W2 = C2 + D2 - E2

#A-Bまでの数からC or Dで割り切れる数の個数
W = W2 - W1

print(B-(A-1)-W)

Submission status: Accepted

Solution code:
import fractions

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

def f(x):
  return B//x - (A-1)//x

print( (B - A + 1) - (f(C) + f(D) - f(lcm)) )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A,B,C,D = [int(x) for x in input().split()]
def gdc(x,y):
  if x%y == 0:
    return y
  else:
    return gdc(y,x%y)
g = C*D//gdc(D,C)
count= B-A+1-B//C+(A-1)//C-B//D+(A-1)//D+B//g-(A-1)//g
print(count)

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = [int(i) for i in input().split()]
A = A - 1
l = (C * D) // fractions.gcd(C,D)

b_sum = B -(B//C) - (B//D) + (B//l)
a_sum = A - (A//C) - (A//D) + (A//l)

print(b_sum - a_sum)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def gcd(x, y):
    if x<y: x, y = y, x
    while y: x, y = y, x%y
    return x

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

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

Submission status: Accepted

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

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

def main():
    A, B, C, D = map(int, readline().rstrip().split())
    CD = lcm_base(C, D)
    ans = B - (B//C + B//D - B//CD)
    ans -= ((A-1) - ((A-1)//C + (A-1)//D - (A-1)//CD))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def main():
    A, B, C, D = map(int, readline().rstrip().split())
    ans = B - (B//C + B//D - B//lcm_base(C, D))
    ans -= ((A-1) - ((A-1)//C + (A-1)//D - (A-1)//lcm_base(C, D)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
lcm = c*d//gcd(c,d)
dis = b-a
l = [c,d,lcm]
ans = []
for i in range(3):
  if a % l[i] == 0:
    ans.append(dis//l[i]+ 1)
  elif l[i] < a:
    ans.append((dis + a%l[i])//l[i])
  elif a < l[i] <= b:
    ans.append((b-l[i])//l[i] + 1)
  else:
    ans.append(0)
print(dis + 1 - ans[0] - ans[1] + ans[2])

Submission status: Accepted

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

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

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

s = b // c - a // c
t = b // d - a // d
LCM = lcm(c, d)
both = b // LCM - a // LCM
ans = (b - a) - s - t + both
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())
a-=1
print((b-a)-(b//c+b//d-b//lcm(c,d))+(a//c+a//d-a//lcm(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)
x = b - (b // c) - (b // d) + (b // lcm)
y = (a - 1) - ((a - 1) // c) - ((a - 1) // d) + ((a - 1) // lcm)
print(x - y)

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

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

#A-1
A1 = (a-1) - (a-1)//c -(a-1)//d +(a-1)//(c*d//cd)
 
#Bまで
B = b - b//c - b//d +b//(c*d//cd)
 
print(B-A1)

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())
SUM = B - A + 1
c = (B // C - (A - 1) // C)
d = (B // D - (A - 1) // D)
cd = (B // lcm(C, D) - (A - 1) // lcm(C, D))
print(B - A + 1 - (B // C - (A - 1) // C + B // D - (A - 1) // D - (B // lcm(C, D) - (A - 1) // lcm(C, D))))

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())
SUM = B - A + 1
c = (B // C - (A - 1) // C)
d = (B // D - (A - 1) // D)
cd = (B // lcm(C, D) - (A - 1) // lcm(C, D))
print(B - A + 1 - (B // C - (A - 1) // C + B // D - (A - 1) // D - 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, input().split())
SUM = B - A + 1
c = (B // C - (A - 1) // C)
d = (B // D - (A - 1) // D)
cd = (B // lcm(C, D) - (A - 1) // lcm(C, D))
print(SUM - (c + d - cd))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
import math
import fractions
def main():
    A, B, C, D = map(int, input().split())
    
    n_U = (B-A+1)
    n_C = B//C - (A-1)//C
    n_D = B//D - (A-1)//D
    LCM = (C*D)//fractions.gcd(C, D)
    n_CD = B//LCM - (A-1)//LCM
    
    print(n_U - n_C - n_D + n_CD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())
a, b, c, d = map(int, input().split())

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

Submission status: Accepted

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

under_a = (a-1)//c + (a-1)//d - (a-1)//lcm_cd
under_b = b//c + b//d - b//lcm_cd
print(ans-(under_b-under_a))

Submission status: Accepted

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

cd = C*D//gcd(D,C)
f = lambda x: B//x - ((A-1)//x)
print(B - A + 1 - (f(C) + f(D) - f(cd)))

Submission status: Accepted

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

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)

underA = (A-1) // C + (A-1) // D - (A-1) // int(lcm(C,D))
underB = B // C + B // D - B // lcm(C,D)
N = underB - underA
print(B-A+1-N)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = list(map(int,input().split()))
#ベン図を描いてみれば一目瞭然。全要素unをA以上B以下の整数とする。
#そこからCで割り切れる要素数cnとDで割り切れる要素数dnを引き
#最後にCD両方で(=C,Dの最小公倍数で)割り切れる要素数enを足す

#全要素数un
un = B - A + 1
#Cで割り切れる要素数cn
cn = B//C - (A-1)//C 
#Dで割り切れる要素数dn
dn = B//D - (A-1)//D
#CでもDでも割り切れる要素数en
E = C * D / int(gcd(C, D)) #CとDの最小公倍数
E = int(E)
en = B//E - (A-1)//E
#結果
ans = un - (cn + dn) + en
print(int(ans))

Submission status: Accepted

Solution code:

import math
from  fractions import gcd

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

A,B,C,D = map(int,input().split())
d_cnt = B//D-(A-1)//D
c_cnt = B//C-(A-1)//C
cd = lcm(C,D)
cd_cnt = B//cd-(A-1)//cd
print(B-A+1-(c_cnt+d_cnt-cd_cnt))

Submission status: Accepted

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

from fractions import gcd
def f(n):
    #cとdの約数の個数をxに入れる
    x = n//c
    x += n//d
    #最小公倍数の約数を引く　例えば3,5であれば15の倍数を引く15,30,45...
    lcm = c*d // gcd(c,d)
    x -= n // lcm
    #どちらでも割れない
    return n-x

ans = f(b) - f(a-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

#count1=0
#count2=0
#for i in range(A,B+1):
#  if i%C!=0 and i%D!=0:
#    count+=1
#print(count)

e=B//C
f=B//D
g=(A-1)//C
h=(A-1)//D
i=e-g
j=f-h

P=gcd(C,D)
L=C*D//P
k=(A-1)//L
m=B//L
n=m-k

print(B-A+1-i-j+n)

Submission status: Accepted

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

d1 = b//c - a//c
d2 = b//d - a//d
add = b//lcm - a//lcm
if a % c == 0:
    d1 += 1
if a % d == 0:
    d2 += 1
if a % lcm == 0:
    add += 1

print(total-d1-d2+add)

Submission status: Accepted

Solution code:
def gcd(x, y):
  while y!=0:
    x, y = y, x%y
  return x
def lcd(x, y):
    return x*y//gcd(x,y)
def C():
    a,b,c,d = list(map(int, input().split()))
    c_divide = b//c - (a-1)//c
    d_divide = b//d - (a-1)//d
    cd_lcd = lcd(c,d)
    lcd_divide = b//cd_lcd - (a-1)//cd_lcd
    print(b-a+1 - c_divide - d_divide + lcd_divide)
C()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def myAnswer(A:int,B:int,C:int,D:int) -> int:
   divC = B//C - (A - 1)//C 
   divD = B//D - (A - 1)//D
   divCD = B//lcm(C,D) - (A - 1)//lcm(C,D) 
   # print(divC,divD,divCD)
   return (B - A + 1) - (divC + divD - divCD)

def modelAnswer():
   return
def main():
   A,B,C,D = map(int,input().split())
   print(myAnswer(A,B,C,D))

if __name__ == '__main__':
   main()

Submission status: Accepted

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

Submission status: Accepted

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

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

main()


# 1 2 3 4 5
# 1 3 3 4 5
# 1 4 3 4 5

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    a, b, c, d = mi()
    m = c * d // gcd(c, d)
    one_to_a_minus_1 = (a-1) - ((a-1)//c + (a-1)//d - (a-1)//m)
    one_to_b = b - (b//c + b//d - b//m)
    print(one_to_b - one_to_a_minus_1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


t = b//c + b//d - b//(c*d//g)
l = (a - 1)//c + (a - 1)//d - (a - 1)//(c*d//g)
ans = b - (a - 1) - t + l

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-A+1)-(b-a))

Submission status: Accepted

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


def calc(x, n):
    return x // n


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


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

Submission status: Accepted

Solution code:
#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-RemainderMinimization.py
#
# import math
from fractions import gcd
a, b, c, d = map(int, input().split())
# cd_lcm = (c * d) // math.gcd(c, d)
cd_lcm = (c * d) // gcd(c, d)
ab_c = b//c - (a-1)//c
ab_d = b//d - (a-1)//d
ab_cd_both = b//cd_lcm - (a-1)//cd_lcm
ab_cd_either = ab_c + ab_d - ab_cd_both
ab_cd_neither = b-a+1 - ab_cd_either

print(ab_cd_neither)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
p = b//c - (a-1)//c 
q = b//d - (a-1)//d 
#a,bの最小公倍数
def lcm(a, b):
  return a * b // fractions.gcd (a, b)
e = lcm(c, d)
r = b//e - (a-1)//e 
f = b - a + 1
p = f - p
q = f - q
r = f - r

print((p+q-r))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int, input().split())
x = (c*d) // gcd(c,d)
c1, d1, cd1 = b // c, b // d, b // x
c2, d2, cd2 = (a-1) // c, (a-1) // d, (a-1) // x
ans = (c1+d1-cd1) - (c2+d2-cd2)
print(b-a+1-ans)

Submission status: Accepted

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

# math.ceil(a/b)->(a+b-1)//b

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

c_num = b // c - (a - 1) // c
d_num = b // d - (a - 1) // d

c_d_lcm = c * d // gcd(c, d)
c_d_num = b // c_d_lcm - (a - 1) // c_d_lcm

ans = b - a + 1 - c_num - d_num + c_d_num
print(ans)

Submission status: Accepted

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

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

def div_n(a,b,n):
    if a%n != 0:
        marker1 = a + (n - a%n)
    else:
        marker1 = a
        
    if b%n != 0:
        marker2 = b - (b%n)
    else:
        marker2 = b
    return (marker2 - marker1)//n + 1

all_cnt = (b-a)+1
a_cnt = div_n(a,b,c)
b_cnt = div_n(a,b,d)
c_cnt = div_n(a,b,lcm(c,d))

print(all_cnt - a_cnt - b_cnt + c_cnt)

Submission status: Accepted

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

Submission status: Accepted

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

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

C_count = B // C - A // C
if A % C == 0:
    C_count += 1
D_count = B // D - A // D
if A % D == 0:
    D_count += 1
CD_count = B // lcm(C, D) - A // lcm(C, D)
if A % lcm(C, D) == 0:
    CD_count += 1
div_count = C_count + D_count - CD_count
ans = B - A + 1 - div_count
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)
ans = 0
ans += B-B//C-B//D+B//E
ans -= A-1-(A-1)//C-(A-1)//D+(A-1)//E
print(ans)

Submission status: Accepted

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

lcm=(c*d)//fractions.gcd(c,d)
def q(n):
    sc=n//c
    sd=n//d
    s=n//lcm
    w=sc+sd-s
    return n-w

print(q(b)-q(a-1))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
count=0
def cc(a,b,c):
    if a%c==0:
        k=a
    else:
        k=a+c-(a%c)
    return ((b//c)-(k//c)+1)
print(b-a+1-cc(a,b,c)-cc(a,b,d)+cc(a,b,(c*d)//fractions.gcd(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)
# a-1以下でcでもdでも割り切れない
ans_a = a-1 - (a-1) // c - (a-1) // d + (a-1) // lcm
# b以下でcでもdでも割り切れない
ans_b = b - b // c - b // d + b // lcm
print(ans_b - ans_a)

Submission status: Accepted

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

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


print(ans+1)

Submission status: Accepted

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

Submission status: Accepted

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

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

L = lcm(C, D)

def f(X):
    return X - (X//C + X//D - X//L)

num = f(B) - f(A-1)

print(num)

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
m = c*d//fractions.gcd(c, d)
ans = b - b//c - b//d + b//m
b = a-1
ans -= b - b//c - b//d + b//m
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 -= 1
ans1 = b - b//c - b//d + b//lcm
ans2 = a - a//c - a//d + a//lcm
print(ans1 - ans2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

def gcd(a, b):
    """
    Greatest Common Divisor
    Euclidean Algortihm
    """
    if a < b:
        gcd(b, a)
    while b != 0:
        a, b = b, a % b
    return a

INF = float('inf')
NIL = - 1


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


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

if A % C != 0:
    c_count = (B // C) - (A // C)
else:
    c_count = (B // C) - (A // C) + 1

if A % D != 0:
    d_count = (B // D) - (A // D)
else:
    d_count = (B // D) - (A // D) + 1


lcm = lcm(C, D)
if A % lcm != 0:
    lcm_count = (B // lcm) - (A // lcm)
else:
    lcm_count = (B // lcm) - (A // lcm) + 1


print(total - c_count - d_count + lcm_count)

Submission status: Accepted

Solution code:
#Satoooh
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:
#@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)#Fは両方で割り切れる、最小公倍数で割り切れる
    return A-D-E+F#包除原理
ans = count(b, c, d) - count(a-1, c, d)
#A以上B以下の整数のうち、CでもDでも割り切れないものの個数
#Aを引く１することで、A以上が分かる
#if(a % c != 0 and a % d != 0):
    #ans += 1#AがCでもDでも割り切れないなら、足す１
print(ans)