Problem:


Score : 300 points

Problem Statement

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

Constraints

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

1\leq C,D\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

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

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
from math import ceil

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

def num(l,r,n):
    return r//n-(l-1)//n

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

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

Submission status: Accepted

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

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

def div2(x):
  return div(x,b)-div(x,a-1)
  
print(b-a+1-div2(c)-div2(d)+div2(c*d//fr.gcd(c,d)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int,input().split())
def gcd(a,b):
    if b>a:
        b,a=a,b
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def warikiri(n,c,d):
    koubai=(c*d)//gcd(c,d)
    return n-n//d-n//c+n//koubai
print(warikiri(b,c,d)-warikiri(a-1,c,d))

Submission status: Accepted

Solution code:
import fractions

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

def div(a,c,d):
    ac=a//c
    ad=a//d
    cd=c*d//fractions.gcd(c,d)
    acd=a//cd
    return ac+ad-acd

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

Submission status: Accepted

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

ans = b-a+1

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

c_mul_nums = b//c - (a-1)//c
d_mul_nums = b//d - (a-1)//d
cd_mul_nums = b//lcm - (a-1)//lcm

print(ans - c_mul_nums - d_mul_nums + cd_mul_nums)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b,c,d = (int(i) for i in input().split())
x = c
y = d
if x<y:
  tmp = x
  x = y
  y = tmp
r = x%y
while r>0:
  x = y
  y = r
  r = x%y
m = c*d//y
n = b//m - (a+m-1)//m + 1
c0 = b//c - (a+c-1)//c + 1
d0 = b//d - (a+d-1)//d + 1
ans = (b-a+1) - (c0+d0) + n
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

B2=B-B//C-B//D+B//lcm(C,D)
A2=(A-1)-(A-1)//C-(A-1)//D+(A-1)//lcm(C,D)

print(B2-A2)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        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 * b // gcd(a, b)

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

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


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
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)

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

print(ans - ans1)

Submission status: Accepted

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

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

b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
print((B-(A-1))-(b_num-a_num))

Submission status: Accepted

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

def divisor(x, c, d):
    cd = c * d // fractions.gcd(c, d) 
    ans = x - (x // c + x // d - x // cd)
    return ans

B_divisor = divisor(B, C, D)
A_divisor = divisor(A-1, C, D)
print(B_divisor-A_divisor)

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
"""f(b)-f(a-1)を出力すればいい"""
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)
ans = b - (b//c + b//d -b//lcm(c,d))
ans1 = (a-1) - ((a-1)//c + (a-1)//d - (a-1)//lcm(c,d)) 

print(ans-ans1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

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

def chk(s,e,d):
	return(e//d-s//d)

#最大公約数
import fractions
e = c*d//fractions.gcd(c,d)

print(b-(a-1) -chk(a-1,b,c) -chk(a-1,b,d) +chk(a-1,b,e))
#print(chk(a-1,b,c))
#print(chk(a-1,b,d))
#print(chk(a-1,b,e))

Submission status: Accepted

Solution code:
import sys
 
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 main():
    A, B, C, D = map(int, input().split())
    Aone = A - 1
    CDlcm = lcm(C, D)
 
    Bc = B // C
    Bd = B // D
    Blcm = B // CDlcm
    Bdec = B - Bc - Bd + Blcm
 
#    print(Bc,Bd,Blcm)
 
    Ac = Aone // C
    Ad = Aone // D
    Alcm = Aone // CDlcm
    Adec = Aone - Ac - Ad + Alcm
 
#    print(Ac,Ad,Alcm)
 
    print(Bdec - Adec)
 
 
main()

Submission status: Accepted

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


def main():
    A, B, C, D = map(int, input().split())
    Aone = A - 1
    CDlcm = int(C /  fractions.gcd(C, D) * D)

    Bc = B // C
    Bd = B // D
    Blcm = B // CDlcm
    Bdec = B - Bc - Bd + Blcm

#    print(Bc,Bd,Blcm)

    Ac = Aone // C
    Ad = Aone // D
    Alcm = Aone // CDlcm
    Adec = Aone - Ac - Ad + Alcm

#    print(Ac,Ad,Alcm)

    print(Bdec - Adec)


main()

Submission status: Accepted

Solution code:
import sys

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 main():
    A, B, C, D = map(int, input().split())
    Aone = A - 1
    CDlcm = lcm(C, D)

    Bc = B // C
    Bd = B // D
    Blcm = B // CDlcm
    Bdec = B - Bc - Bd + Blcm

#    print(Bc,Bd,Blcm)

    Ac = Aone // C
    Ad = Aone // D
    Alcm = Aone // CDlcm
    Adec = Aone - Ac - Ad + Alcm

#    print(Ac,Ad,Alcm)

    print(Bdec - Adec)


main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

a, b, c, d = na()
l = lcm(c, d)

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

w = b - a + 1
print(w - n(c) - n(d) + n(l))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
import fractions
lcm=c*d//fractions.gcd(c,d)
#1~Bの中
count=b-(b//c+b//d)+b//lcm

#1~A-1の中
temp_count=a-1-((a-1)//c+(a-1)//d)+(a-1)//lcm
print(count-temp_count)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

l = lcm(c, d)
divc = b // c - a // c
divd = b // d - a // d
divl = b // l - a // l

print(b - a - divc - divd + divl)

Submission status: Accepted

Solution code:
from fractions import gcd


def count(X, C, D, l):
    c = X // C
    d = X // D
    cd = X // l
    return c + d - cd


def main():
    A, B, C, D = map(int, input().split(" "))
    lcm = C * D // gcd(C, D)
    BorC = B - A + 1 - count(B, C, D, lcm) + count(A - 1, C, D, lcm)
    print(BorC)


if __name__ == '__main__':
    main()

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())
b_num = B//C + B//D - B//lcm(C,D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C,D)

print((B-A+1) - (b_num - a_num))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
cdiv = c
ddiv = d
while ddiv > 0:
  cdiv, ddiv = ddiv, cdiv % ddiv
M = c*d//cdiv

mnd = M-(c+d)//cdiv+1
ad = (a-1) % M
bd = b % M

print(mnd*(b//M)+bd-bd//c-bd//d-mnd*((a-1)//M)-ad+ad//c+ad//d)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
import fractions
#cとdの最小公倍数
lcm=c*d//fractions.gcd(c,d)
count1=b-(b//c+b//d-b//lcm)
count2=(a-1)-((a-1)//c+(a-1)//d-(a-1)//lcm)

print(count1-count2)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = list(map(int, input().split()))
num_B_C = B // C
num_B_D = B // D
lcm_C_D = int(C * D / gcd(C, D))
num_B = B - (num_B_C + num_B_D) + B // lcm_C_D

num_A_C = (A-1) // C
num_A_D = (A-1) // D
num_A = (A-1) - (num_A_C + num_A_D) + (A-1) // lcm_C_D

ans = num_B - num_A
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

Solution code:
import fractions
#import math はpython3.5以降であることに注意

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

#b_minus_a = b-a


#基本方針：bまでの解を求め、その後に(a-1)までの解を差し引く
#　　　　　その残りがこの問題の解

cnt = b - int((b // c)) - int((b // d))

#cとdの最小公倍数を求める
cnt = cnt + (b // int(c*d / fractions.gcd(c,d)))

cnt_a = (a-1) - int( ( (a-1) // c ) ) - int( ( (a-1) // d) )
cnt_a = cnt_a + ((a-1) // int(c*d / fractions.gcd(c,d)))

cnt = cnt - cnt_a


#考え方は正しいが、時間超過
#i = 1
#while( i * d < b_minus_a ):
#  if( i * d % c != 0 ):
#    cnt -= 1
#  
#  i += 1
  
print(cnt)

Submission status: Accepted

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


m1 = (a-1)//c
m2 = (a-1)//d
m3 = b//c
m4 = b//d


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

m5 = c*d//gcd(max(c,d),min(c,d))

m6 = (a-1)//m5
m7 = b//m5

ans = (b-a+1)-((m3-m1)+(m4-m2)-(m7-m6))
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

ac1,ac2 = a//c,a%c
ad1,ad2 = a//d,a%d
bc1,bc2 = b//c,b%c
bd1,bd2 = b//d,b%d
acd1,acd2 = a//cd,a%cd
bcd1,bcd2 = b//cd,b%cd

if ac2 == 0:
    a_ = bc1-ac1+1
else:
    a_ = bc1-ac1

if ad2 == 0:
    b_ = bd1-ad1+1
else:
    b_ = bd1-ad1

if acd2 == 0:
    c_ = bcd1-acd1+1
else:
    c_ = bcd1-acd1

print(b-a+1-(a_+b_-c_))

Submission status: Accepted

Solution code:
import fractions


def func(n, c, d):
    x = n // c
    y = n // d
    z = n // (c * d // fractions.gcd(c, d))

    return n - x - y + z


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

print(func(b, c, d) - func(a - 1, 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())

i = (b // c) - (a // c) 
if(a % c == 0):
  i += 1

j = (b // d) - (a // d)
if(a % d == 0):
  j += 1
  
k = (b // lcm(c,d)) - (a // lcm(c,d))
if(a % lcm(c,d) == 0):
  k += 1

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

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())
count = 0
i = b//c - a//c 
if(a%c == 0):
  i += 1
j = b//d - a//d
if(a%d == 0):
  j += 1
k = b//lcm(c,d) - a//lcm(c,d)
if(a%lcm(c,d) == 0):
  k += 1

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

Submission status: Accepted

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

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

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

# CとDの最大公約数
E = lcm(C, D)

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

print(B - A + 1 - F)

Submission status: Accepted

Solution code:
import fractions

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

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

ansb = b // c + b // d - b // lcm
ansa = a // c + a // d - a // lcm

print(b - ansb - (a - ansa))

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
numA = A - (A // C + A // D - A // lcm)
numB = B - (B // C + B // D - B // lcm)

print(numB - numA)

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

#Bで割り切れれない数 = B - Bで割り切れる数
_not_Divisible_number_B = B - (B//C + B//D - B//lcm(C,D))

#A以上B以下なので
lowA =  A -1

_not_Divisible_number_A_1 = lowA - (lowA//C + lowA//D - lowA//lcm(C,D))

ans = _not_Divisible_number_B - _not_Divisible_number_A_1

print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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


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)


def interval(a, b, c):
    a1 = (a-1)//c
    b1 = b//c
    return b1 - a1


l = lcm(c, d)

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

Submission status: Accepted

Solution code:
import fractions


def anti_division(n, d1, d2):
    g = fractions.gcd(d1, d2)
    l = (d1 * d2) // g
    ret = n - (n//d1 + n//d2) + n//l
    return ret


a, b, c, d = [int(i) for i in input().split()]
ans = anti_division(b, c, d) - anti_division(a - 1, c, d)
print(ans)

Submission status: Accepted

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

def how_many(a, b, c):
    A, B = (a-1)//c, b//c
    return B-A

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)

cm = how_many(a, b, c)
dm = how_many(a, b, d)
cdm = how_many(a, b, lcm(c, d))
print(b-a+1-(cm+dm)+cdm)

Submission status: Accepted

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

c_count = b // c - (a - 1) // c
d_count = b // d - (a - 1) // d
e_count = b // e - (a - 1) // e

ans = b - a + 1 - c_count - d_count + e_count
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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


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


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

Submission status: Accepted

Solution code:
from fractions import gcd

A, B, C, D = map(int, open(0).read().split())
k = (C*D)//gcd(C,D)

def calc(x):
    q = (x//C)+(x//D)-(x//k)
    return x-q

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

Submission status: Accepted

Solution code:
# import math
import fractions

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


# upper 以下で div で割り切れるものの個数
def num_divisor(upper, div):
    return upper // div


# upper 以下で c でも d でも割り切れないものの個数
def num_divisor_c_d(upper, c, d):
    # gcd_cd = c * d // math.gcd(c, d)
    gcd_cd = c * d // fractions.gcd(c, d)

    n1 = num_divisor(upper, c)
    n2 = num_divisor(upper, d)
    n12 = num_divisor(upper, gcd_cd)

    return upper - (n1 + n2 - n12)


ans = num_divisor_c_d(b, c, d) - num_divisor_c_d(a - 1, c, d)

print(ans)

Submission status: Accepted

Solution code:
# 最小公倍数を返す
def euclid(x, y):
    x_1 = x
    y_1 = y
    a = x_1%y_1
    while a != 0:
        x_1 = y_1
        y_1 = a
        a = x_1%y_1
    return (x * y) // y_1

# x以下のCとDで割り切れる数を返す
def dif(x, C, D):
    return x - (x//C) - (x//D) + (x//(euclid(C, D)))

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

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

Submission status: Accepted

Solution code:
import fractions

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

def dif(x, C, D):
    return x - (x//C) - (x//D) + (x//(euclid(C, D)))

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d=map(int,input().split())
def lcm(n,m):
    return (n*m)//gcd(n,m)
cntb=b-(b//c)-(b//d)+(b//lcm(c,d))
cnta=a-1-(a-1)//c-((a-1)//d)+((a-1)//lcm(c,d))
ans=cntb-cnta
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from fractions import gcd

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

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

def count_prime(x):
    return (b // x) - ((a-1) // x)

print((b-a+1) - (count_prime(c) + count_prime(d) - count_prime(l)))

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
nC = B//C - (A-1)//C
nD = B//D - (A-1)//D
lcm_CD = lcm(C, D)
nCD = B//(lcm_CD) - (A-1)//(lcm_CD)

print(N - nC - nD + nCD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd
def lcm(a, b):
    return a*b // gcd(a, b)
def group(s, t, u):
    su = (s - 1) // u
    tu = t // u
    return  tu - su

A, B, C, D = map(int, input().split())
ABC = group(A, B, C)
ABD = group(A, B, D)
ABCD = group(A, B, lcm(C,D))
U = B - A + 1
print(U-(ABC+ABD-ABCD))

Submission status: Accepted

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

x, y = c, d
r = x % y
while r != 0:
    x, y = y, r
    r = x % y
gcd = y
lcm = c * d // gcd

nc = b // c - (a - 1) // c
nd = b // d - (a - 1) // d
nlcm = b // lcm - (a - 1) // lcm

print((b - a + 1) - (nc + nd - nlcm))

Submission status: Accepted

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

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

CD = C * D // gcd(C, D)
A -= 1

A_div = A - (A // C + A // D - A // CD)
B_div = B - (B // C + B // D - B // CD)

print(B_div - A_div)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

import fractions

def ri():
    return int(input())

def rl():
    return list(input().split())

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

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

def main():
    a, b, c, d = rli()
    nb = calc(b, c, d)
    na = calc(a-1, c, d)
    # print(nb, na)
    print(nb-na)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

X=C*D//fractions.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:
import fractions

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

c_min = -(-a // c)
c_max = (b // c)
d_min = -(-a // d)
d_max = (b // d)
lcm_min = -(-a // cd_lcm)
lcm_max = (b // cd_lcm)

c_quantity = c_max - c_min + 1
d_quantity = d_max - d_min + 1
lcm_quantity = lcm_max - lcm_min + 1

print((b - a + 1) - c_quantity - d_quantity + lcm_quantity)

Submission status: Accepted

Solution code:
import fractions

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

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

c_divide = (B // C) - ((A - 1) // C)
d_divide = (B // D) - ((A - 1) // D)
cd_divide = (B // lcm(C, D)) - ((A - 1) // lcm(C, D))
ans = (B - A + 1) - c_divide - d_divide + cd_divide
print(max(ans, 0))

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
c, d = C, D
while d != 0:
  c, d = d, c % d
L = (C * D) // c
AX, AY, AZ = (A - 1) // C, (A - 1) // D, (A - 1) // L
BX, BY, BZ = B // C, B // D, B // L

ACS = A - 1 - AX - AY + AZ
BCS = B - BX - BY + BZ

print(BCS - ACS)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc131/tasks/abc131_c
# A~Bと言われたら、0~B と 0~Aの個数で成り立つのではないか？と考える典型問題

from fractions import gcd


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


def f(n, c, d):
    # nを含んでcでもdでも割り切れる数の個数を返す
    return n // c + n // d - n // lcm(c, d)


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

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

total = b - a + 1

c_1 = b//c - a//c if a%c!=0 else b//c - a//c + 1
d_1 = b//d - a//d if a%d!=0 else b//d - a//d + 1

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

div = int(c * d / gcd(c, d))

cd = b//div - a//div if a%div!=0 else b//div - a//div + 1

print(total - c_1 - d_1 + cd)

Submission status: Accepted

Solution code:

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


A,B,C,D = map(int,input().split())
mul = C*D//gcd(C,D)
mi = (A-1) // mul
ma = B // mul
mv = ma-mi
#print(mv)
ci = (A-1) // C
ca = B // C
cv = ca-ci
#print(cv)
di = (A-1) // D
da = B // D
dv = da-di
#print(dv)
print(B-A-cv-dv+mv+1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import fractions
def input(): return sys.stdin.readline().rstrip()

def main():
    a, b, c, d = map(int, input().split())
    cd_gcd = c * d // fractions.gcd(c, d)
    cnt = lambda n: n - n // c - n // d + n // cd_gcd
    print(cnt(b) - cnt(a-1))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

b_not_division = B - B//C - B//D + B//((C*D)//gcd(C, D))
a_mins_one_not_division = (A-1) - (A-1)//C - (A-1)//D + (A-1)//((C*D)//gcd(C, D))
print(b_not_division-a_mins_one_not_division)

# # 以下で、CでもDでも割り切れない数の個数を求める
# b_not_division = B - (B//C + B//D - B//(C*D//gcd(C, D)))
# # A-1以下で、CでもDでも割り切れない数の個数を求める
# a_minus_one_not_division = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//(C*D)//gcd(C, D))
# print(b_not_division-a_minus_one_not_division)

Submission status: Accepted

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

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

def ko(x):
  a1=x//c
  a2=x//d
  return x-(a1+a2-x//lcm(c,d))

print(ko(b)-ko(a-1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

count=b-a+1-num_c-num_d+num_e
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def pgcd(m,n): 
    while m%n: 
        r=m%n 
        m=n 
        n=r 
    return n 
 
def ppcm(m,n): 
    return m*n//pgcd(m,n)


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

mx=max(c,d)
mn=min(c,d)
e=ppcm(c,d)

x=b//mx-(a-1)//mx
y=b//mn-(a-1)//mn
z=b//e-(a-1)//e
print(b-a+1-x-y+z)

Submission status: Accepted

Solution code:
import fractions

def lcm(x,y):
	return (x*y)//fractions.gcd(x,y)
count = 0
A,B,C,D= map(int,input().split())
lcm = lcm(C,D)
E = (A-1)//C
F = (A-1)//D
G = (A-1)//lcm
H = B//C
I = B//D
J = B//lcm

count = (B-A+1)-((H-E)+(I-F)-(J-G))

print(count)

Submission status: Accepted

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


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


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

l = lcm(C, D)
num_B = B // C + B // D - B // l
num_A = A // C + A // D - A // l
print(B - num_B - A + num_A)

Submission status: Accepted

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

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

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

ac = int((A-1)//C)
ad = int((A-1)//D)
bc = int(B//C)
bd = int(B//D)

c = bc - ac
d = bd - ad

baisu = lcm(C,D)
a_baisu = int((A-1)//baisu)
b_baisu = int(B//baisu)
print(B-A+1-c-d+(b_baisu-a_baisu))

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

lcm_cd = lcm(c,d)

min_a_c = (a-1)//c
min_a_d = (a-1)//d
min_a_lcm = (a-1)//lcm_cd
max_b_c = b//c
max_b_d = b//d
max_b_lcm = b//lcm_cd

ans=(b-a+1)-((max_b_c-min_a_c)+(max_b_d-min_a_d)-(max_b_lcm-min_a_lcm))


print(ans)

Submission status: Accepted

Solution code:
import math


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


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


A, B, C, D = map(int, input().split())
t = lcm(max(C, D), min(C, D))
m = (B // C - (A - 1) // C) + (B // D - (A - 1) // D) - (B // t - (A - 1) // t)
print((B - A + 1) - m)

Submission status: Accepted

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

def caluclate(a, b, c, d):

    s1 = (a - 1) // c
    s2 = (a - 1) // d

    m1 = s2 + s1

    s3 = b // c
    s4 = b // d

    m2 = s4 + s3

    common = int(smallestCommon(c,d))

    m3 = (b // common) - (a-1)//common

    total = int(b - a + 1)

    return total - (m2 - m1 - m3)


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

result = caluclate(A,B,C,D)

print(result)

Submission status: Accepted

Solution code:
#ABC_131_C
import fractions
A,B,C,D=list(map(int,input().split()))
#B以下の答え
CD_lcm=C*D//fractions.gcd(C,D)

underB=B-B//C-B//D+B//CD_lcm
underA_1=A-1-(A-1)//C-(A-1)//D+(A-1)//CD_lcm

print(underB-underA_1)

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

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

Submission status: Accepted

Solution code:
#ABC-131-C
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
    
A, B, C, D = map(int, input().split())
lcm = C * D // gcd(C, D)
#1~A-1までの数字でCでもDでも割り切れないものの個数
A_divided_C = (A-1) // C
A_divided_D = (A-1) // D
A_divided_CD = (A-1) // (lcm)
one_to_A = (A-1) - A_divided_C - A_divided_D + A_divided_CD

#1~Bまでの数字でCでもDでも割り切れないものの個数
B_divided_C = B // C
B_divided_D = B // D
B_divided_CD = B // (lcm)
one_to_B = B - B_divided_C - B_divided_D + B_divided_CD

ans = one_to_B - one_to_A
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

cs = (a-1) // c + 1
ce = b // c
cc = ce - cs + 1

ds = (a-1) // d + 1
de = b // d
dc = de - ds + 1

cd = lcm(c, d)
cds = (a-1) // cd + 1
cde = b // cd
cdc = cde - cds + 1


ans = b - a + 1 - cc - dc + cdc

print(ans)

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())
m=((c*d)//(gcd(c,d)))
di=b-a+1
if a%c==0:
  c1=(b//c-a//c)+1
else:
  c1=(b//c-a//c)
if a%d==0:
  c2=(b//d-a//d)+1
else:
  c2=(b//d-a//d)
if a%m==0:
  c3=(b//m-a//m)+1
else:
  c3=(b//m-a//m)
print(di-(c1+c2-c3))

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())
m=((c*d)//(gcd(c,d)))
di=b-a+1
c1=(b//c-(a-1)//c)
c2=(b//d-(a-1)//d)
c3=(b//m-(a-1)//m)
print(di-(c1+c2-c3))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
x1=b//c-(a-1)//c #ｃの割れるやつ
x2=b//d-(a-1)//d #ｄの割れるやつ
sks=c * d // fractions.gcd(c,d)#最小公倍数　普通ならmathメソッドにある
x3=b//sks-(a-1)//sks#ｃ＊ｄの割れるやつ
ans=b-a+1-(x1+x2-x3)
print (ans)

Submission status: Accepted

Solution code:
import fractions

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

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

b_count=b-(b//c+b//d-b//cd_lcm)
a_count=a-1-((a-1)//c+(a-1)//d-(a-1)//cd_lcm)

print(b_count-a_count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import fractions

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

def solve(A: int, B: int, C: int, D: int):

    # n以下のCでもDでも割り切れない数を返す
    def counter(n):
        c_ct=n//C
        d_ct =n//D
        cd_ct=n//lcm(C,D)
        return n-c_ct-d_ct+cd_ct
    
    print(counter(B)-counter(A-1))

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


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


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


def main():
    ans = (B-A+1) - f(C) - f(D) + f(lcm(C, D))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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