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
sys.setrecursionlimit(10 ** 6)

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)


a, b, c, d = map(int, input().split())
u = b - a + 1
x = b // c - (a - 1) // c
y = b // d - (a - 1) // d
xy = b // lcm(c, d) - (a - 1) // lcm(c, d)
ans = u - x - y + xy
print(ans)

Submission status: Accepted

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

def gcd(x,y):

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


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

Bika = B - B//C -B//D + B//lcm(C,D)
Aika = A-1 - (A-1)//C -(A-1)//D + (A-1)//lcm(C,D)

print(Bika-Aika)

Submission status: Accepted

Solution code:
import fractions

inputs = [int(i) for i in input().split()]

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

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

l = lcm(c, d)

c1 = b // c
c2 = (a-1) // c
c3 = c1 - c2

d1 = b // d
d2 = (a-1) // d
d3 = d1 - d2

l1 = b // l
l2 = (a-1) // l
l3 = l1 - l2

ans = (b-a+1) - (c3 + d3 - l3)
print(ans)

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split(" "))
if A<1 or B<A or B >10**18 or C<1 or  D > 10**9:
	print ('Illegal')
else:
	a,b=C,D
	if a < b:
		a, b = b, a
	while a % b != 0:
		a, b = b, a % b
	t=int(C*D/b)
	n=B-A+1-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//t-(A-1)//t)
	print(n)

Submission status: Accepted

Solution code:
import fractions

def divcount(a,b,x):
    return b//x - (a-1)//x

a,b,c,d = [int(i) for i in input().split()]
print(b-a+1-(divcount(a,b,c)+divcount(a,b,d)-divcount(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())

adivc = A//C
if A%C != 0:
    adivc = A//C + 1
bdivc = B//C
countC = bdivc - adivc + 1

adivd = A//D
if A%D != 0:
    adivd = A//D + 1
bdivd = B//D
countD = bdivd - adivd + 1

lcm = (int)(C * D / gcd(C, D))
adivlcm = A // lcm
if A%lcm != 0:
    adivlcm = A // lcm + 1
bdivlcm = B // lcm
countlcm = bdivlcm - adivlcm + 1

print(B-A+1-(countC+countD-countlcm))

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


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

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)


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

print(ans)

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
def main():
    A,B,C,D=map(int,input().split())
    if A%C!=0:
        C_min=A-A%C+C
    else:
        C_min=A
    C_max=B-B%C
    if A%D!=0:
        D_min=A-A%D+D
    else:
        D_min=A
    D_max=B-B%D
    mod=C*D//gcd(C,D)
    if A%mod!=0:
        CD_min=A-A%mod+mod
    else:
        CD_min=A
    CD_max=B-B%mod
    C_sum=(C_max-C_min)//C
    D_sum=(D_max-D_min)//D
    CD_sum=(CD_max-CD_min)//mod
    sum= B-A+1-int(C_sum+D_sum-CD_sum+1)
    return sum
print(int(main()))

Submission status: Accepted

Solution code:
def n_mul(m, l, u):
    return u // m - (l-1) // m

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 = [int(i) for i in input().split()]
C = n_mul(c, a, b)
D = n_mul(d, a, b)
CD = n_mul(lcm(c, d), a, b)
ans = (b+1-a) - (C+D-CD)
print(ans)

Submission status: Accepted

Solution code:

def gcd(x, y):
    """Greatest Common Divisor: O(min(x,y,))"""
    if y == 0:
        return x
    return gcd(y, x % y)


def lcm(x, y):
    """Lowest Common Multiple O(min(x,y,))"""
    return x * y // gcd(x, y)


def div_count(x, l, r):
    """Count Divisors"""
    return r // x - (l - 1) // x


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

# solve
div_cd = div_count(c, a, b) + div_count(d, a, b) - div_count(lcm(c, d), a, b)

print(b - a + 1 - div_cd)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
a,b,c,d=map(int,input().split())
cntC=b//c-(a-1)//c
cntD=b//d-(a-1)//d
c1,d1=c,d
if c1<d1:
    c1,d1=d1,c1
while c1%d1!=0:
    c1,d1=d1,c1%d1
d1=int(c*d/d1)
cntCandD=b//d1-(a-1)//d1
ans=int(b - a + 1 - cntC - cntD + cntCandD)
print(ans)

Submission status: Accepted

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


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


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

div_c = (b // c) - ((a - 1) // c)
div_d = (b // d) - ((a - 1) // d)
div_c_and_d = (b // lcm(c, d)) - ((a - 1) // lcm(c, d))
div_c_or_d = div_c + div_d - div_c_and_d
print((b - a + 1) - div_c_or_d)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

A, B, C, D = read_int()

def lcm(a, b):
    pa, pb = a, b
    if a > b:
        a, b = b, a
    while b % a != 0:
        a, b = b % a, a
    return pa * pb // a

def divi(a, b, m):
    ans = 0
    former = a // m
    latter = b // m
    ans = latter - former
    if a % m == 0:
        ans += 1
    return ans

def solve():
    return (B - A + 1) - (divi(A, B, C) + divi(A, B, D) - divi(A, B, lcm(C, D)))

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''Snippets for lcm.
Available functions:
- lcm: Compute least common multiple of a and b.
'''


def lcm(a: int, b: int) -> int:
    '''Compute least common multiple of a and b.
    Args:
        a: Int of number (greater than 0).
        b: Int of number (greater than 0).
    Returns:
        least common multiple.
    Landau notation: O(log n)
    See:
    https://gist.github.com/endolith/114336/eff2dc13535f139d0d6a2db68597fad2826b53c3
    https://docs.python.org/3/library/sys.html#sys.version_info
    '''

    from sys import version_info

    if version_info.major == 3 and version_info.minor >= 5:
        from math import gcd
    else:
        from fractions import gcd

    return a * b // gcd(a, b)


def main():
    a, b, c, d = map(int, input().split())
    l = lcm(c, d)
    x = b // c - (a - 1) // c
    y = b // d - (a - 1) // d
    z = b // l - (a - 1) // l
    w = b - a + 1

    print(w - (x + y - z))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = [int(item) for item in input().split()]
c_div = b // c - (a-1) // c
d_div = b // d - (a-1) // d
lcm = c * d // gcd(c, d)
cd_div = b // lcm - (a-1) // lcm 
print(b - a + 1 - c_div - d_div + cd_div)

Submission status: Accepted

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


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


def cnt(u, x, y):
    return u - (u // x + u // y - u // lcm(x, y))


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

ans = 0

# B以下
ans += cnt(B, C, D)

# A-1以下
ans -= cnt(A - 1, C, D)

print(ans)

Submission status: Accepted

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

def gcd(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp
    while True:
        if x % y == 0:
            break
        x %= y
        tmp = x
        x = y
        y = tmp
    return y

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

devided_c = b // c
devided_c -= (a - 1) // c
devided_d = b // d
devided_d -= (a - 1) // d
devided_cd = b // lcd
devided_cd -= (a - 1) // lcd

ans = (b - a + 1) - (devided_c + devided_d - devided_cd)
print(ans)

Submission status: Accepted

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

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

betweenAandB = B-A+1

cA = (A-1)//C
cB = B//C
cDiv = cB - cA

dA = (A-1)//D
dB = B//D
dDiv = dB - dA

GCD = gcd(C,D)
LCM = C*D//GCD

lcmA = (A-1)//LCM
lcmB = B//LCM
lcmDiv = lcmB - lcmA

ans = betweenAandB - cDiv - dDiv + lcmDiv
print(ans)

Submission status: Accepted

Solution code:
A,B,C,D = map(int, input().split())
def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y % x, x)
def lcm(x,y):
    return x * y // gcd(x,y)
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:
a,b,c,d = map(int, input().split())
def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)
def lcm(x,y):
    return x * y // gcd(x,y)
l = lcm(c,d)
ans_b = b - b//c - b//d + b//l
ans_a = (a-1) - (a-1)//c - (a-1)//d + (a-1)//l
print(ans_b - ans_a)

Submission status: Accepted

Solution code:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
A,B,C,D = input().split()
A = int(A)-1
s = lcm(int(C),int(D))
#s = int(C)*int(D)
#numac = int(A)//int(C)#10//6 = 1
#numad = int(A)//int(D)#10//8 = 1
#numacd = int(A)//s#10//24 = 0
numa = int(A)//int(C) + int(A)//int(D) - int(A)//s
#numa = 1
#numbc = int(B)//int(C)#40//6 = 6
#numbd = int(B)//int(D)#40//8 = 5
#numbcd = int(B)//s#40//24= 1
numb = int(B)//int(C) + int(B)//int(D) - int(B)//s
#numb = 1
print(int(B)-int(A)-(numb - numa))

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

cntC = b // c - (a - 1) // c
cntD = b // d - (a - 1) // d
cntCandD = b // lcm(c, d) - (a - 1) // lcm(c, d)

# print(cntC, cntD, cntCandD)
print(b - a + 1 - cntC - cntD + cntCandD)

Submission status: Accepted

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

def solve(A: int, B: int, C: int, D: int):
    def can_div_by(x: int):
        return (B // x) - (A - 1) // x

    c = can_div_by(C)
    d = can_div_by(D)
    cd = can_div_by(C*D // fractions.gcd(C, D))
    return B - A + 1 - (c + d - cd)

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    print(solve(A, B, C, D))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a, b, c, d = list(map(int, input().split()))
def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)
def lcm(x,y):
    return x * y // gcd(x,y)
def f(n, x):
    return n // x
result = f(b,c) + f(b,d) - f(a-1,c) - f(a-1,d) -f(b,lcm(c,d)) + f(a-1,lcm(c,d))
print(b-a+1-result)

Submission status: Accepted

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

A, B, C, D = map(int, input().split())
L = C * D // gcd(C, D)
c = B // C - (A - 1) // C
d = B // D - (A - 1) // D
l = B // L - (A - 1) // L

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

Submission status: Accepted

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

c=B//C-(A-1)//C
d=B//D-(A-1)//D

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
L=C*D//gcd(C,D)
l=B//L-(A-1)//L
print(int(B-A+1-c-d+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())
e=lcm(c,d)
print((b-a+1)-(b//c-(a-1)//c)-(b//d-(a-1)//d)+(b//e-(a-1)//e))

Submission status: Accepted

Solution code:
import fractions

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

def count(s, f, n):
  return f//n - (s-1)//n

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

print( B-A+1 - ( count(A,B,C) + count(A,B,D) - count(A, B, lcm(C, D)) ) )

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
a,b,c,d = map(int,input().split())
import math
lcm = c*d//gcd(c,d)
a_1 = a-1
panish = ((b//c)+(b//d)-(b//lcm))-(((a_1//c)+(a_1//d))-(a_1//lcm))
print(b-a_1-panish)

Submission status: Accepted

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
A, B, C, D = map(int, input().split())
X = B//C - (A-1)//C
Y = B//D - (A-1)//D
E = (C*D)//gcd(C,D)
Z = B//E - (A-1)//E
print(B-A-X-Y+Z+1)

Submission status: Accepted

Solution code:
#abc131c

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

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

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

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

Submission status: Accepted

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

def lcm(a,b):
    return (a/gcd(a,b))*b
    
A = map(int,raw_input('').split())
a = int(A[0])
b = int(A[1])
c = int(A[2])
d = int(A[3])
l = lcm(c,d)
ans = (b-a+1) - ((b/c) - (a-1)/c) - ((b/d) - (a-1)/d) + ((b/l) - (a-1)/l)
print(ans)

Submission status: Accepted

Solution code:
import fractions

numA, numB, numC, numD = map(int, input().split())

AsplitC = int((numA - 1) // numC)
BsplitC = int(numB // numC)
AsplitD = int((numA - 1) // numD)
BsplitD = int(numB // numD)
AsplitCandD = int((numA - 1) // int(numC * numD // fractions.gcd(numC, numD)))
BsplitCandD = int(numB // int(numC * numD // fractions.gcd(numC, numD)))

count = (numB - numA + 1) - ((BsplitC - AsplitC) + (BsplitD - AsplitD) - (BsplitCandD - AsplitCandD))

print(count)

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)

def g(X):
  return X - X//C - X//D + X//lcm(C,D)

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

ans = g(B) - g(A-1)
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
 
 
def lcd(a, b):
    return a*b // gcd(a, b)
  
a, b, c, d = map(int, input().split())
sum1 = (a - 1) // c + (a - 1) // d - (a - 1) // lcd(c, d)
sum2 = b // c + b // d - b // lcd(c, d)
print(b - a  + 1 - (sum2 - sum1))

Submission status: Accepted

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


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


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

higher = b//c + b//d - b//lcd(c, d)
lower = (a-1)//c + (a-1)//d - (a-1)//lcd(c, d)

print((b-a+1)-higher+lower)

Submission status: Accepted

Solution code:
def calc_gcd(m,n):
    a=max(m,n)
    b=min(m,n)
    r=a%b
    while r>0:
        a=b
        b=r
        r=a%b
    return b

def calc_lcm(m,n):
    return m*n//calc_gcd(m,n)
    
A,B,C,D=map(int,input().split())
c_div=B//C-(A-1)//C
d_div=B//D-(A-1)//D
cd_div=B//calc_lcm(C,D)-(A-1)//calc_lcm(C,D)
print(B-A+1-c_div-d_div+cd_div)

Submission status: Accepted

Solution code:
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n
A, B, C, D = map(int, input().split())
g = C * D // gcd(C, D)
def calc(N):
    return N - (N // C + N // D - N // g)
print(calc(B) - calc(A-1))

Submission status: Accepted

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

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

def getAns(a, b, c):
  num_c = b // c - (a - 1) // c
  return num_c

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

# cについて
num_c =getAns(a,b,c)
#print(num_c)

# dについて
num_d =getAns(a,b,d)
#print(num_d)

# cとdの公倍数について
cd = c * d // gcd(c,d)
num_cd = getAns(a,b,cd)
#print(num_cd)

print(b - a + 1 - (num_c + num_d - num_cd))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

# 割り切れる数を探す


left_c = (a - 1) // c
right_c = b // c

c_count = right_c - left_c

left_d = (a - 1) // d
right_d = b // d

d_count = right_d - left_d


lcm_cd = int(c * d / fractions.gcd(c, d))

left_cd = (a - 1) // (lcm_cd)
right_cd = b // (lcm_cd)

cd_count = right_cd - left_cd

print(b - a + 1 - (c_count + d_count - cd_count))

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())
Max = B-A+1
CD = C*D//(fractions.gcd(C, D))
Ccount = B//C-A//C
Dcount = B//D-A//D
CDcount = B//CD-A//CD
if A % C == 0:
    Ccount += 1
if A % D == 0:
    Dcount += 1
if A % CD == 0:
    CDcount += 1
count = Max+CDcount-Ccount-Dcount
print(count)

Submission status: Accepted

Solution code:
A, B, C, D=(int(x) for x in input().split(" "))
import fractions

def eks(x,a):
    return a//x

def wai(x):
    return eks(x,B)-eks(x,A-1)

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

zet=B-A+1-(wai(C)+wai(D)-wai(lcm(C,D)))
print (zet)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return(a)
A,B,C,D=map(int,input().split())
CD=C*D//gcd(C,D)
print((B-A+1-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//CD-(A-1)//CD)))

Submission status: Accepted

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

a,b,c,d=map(int,input().split())
cn1=0
cn2=0
cn3=0
an1=0
an2=0
an3=0
cnt=0
ans=0
lm=(c*d)//gcd(c,d)

#bまで
cn1=b//c
cn2=b//d
cn3=b//lm
#aまで
an1=(a-1)//c
an2=(a-1)//d
an3=(a-1)//lm
#aからbまで
cn1=cn1-an1
cn2=cn2-an2
cn3=cn3-an3

cnt=cn1+cn2-cn3
ans=b-a-cnt

print(ans+1)

Submission status: Accepted

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

a,b,c,d=map(int,input().split())
cn1=0
cn2=0
cn3=0
an1=0
an2=0
an3=0
cnt=0
ans=0
lm=(c*d)//gcd(c,d)

#bまで
cn1=b//c
cn2=b//d
cn3=b//lm
#aまで
an1=(a-1)//c
an2=(a-1)//d
an3=(a-1)//lm
#aからbまで
cn1=cn1-an1
cn2=cn2-an2
cn3=cn3-an3

cnt=cn1+cn2-cn3
ans=b-a-cnt+1

print(ans)

Submission status: Accepted

Solution code:
def saidaikouyaku(a, b):
    if b > a:
        a, b = b, a

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

A, B, C, D = map(int, input().split())
hani = B - A + 1
Cnum = B // C - (A - 1) // C
Dnum = B // D - (A - 1) // D
saisyoukoubai = C * D // saidaikouyaku(C, D)
koubainum = B // saisyoukoubai - int(A - 1) // saisyoukoubai
#print(hani)
#print(Cnum, Dnum, koubainum, saisyoukoubai)
print(hani - Cnum - Dnum + koubainum)

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return(a)
A,B,C,D=map(int,input().split())
CD=C*D//gcd(C,D)
print((B-A+1-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//CD-(A-1)//CD)))

Submission status: Accepted

Solution code:
import fractions

if __name__ == '__main__':
  a, b, c, d = map(int, input().split(" "))
  c_num = b // c - (a-1) // c
  d_num = b // d - (a-1) // d
  lcm = (c * d) // fractions.gcd(c, d)
  cd_num = b // lcm - (a-1) // lcm
  print(b - a  + 1 - (c_num + d_num - cd_num))

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(' '))
not_a_1 =0
not_b = 0
not_b =  b-(b//c)-(b//d)+(b//lcm(c,d))
not_a_1 = a-1-((a-1)//c)-((a-1)//d)+((a-1)//lcm(c,d))

print(not_b-not_a_1)

Submission status: Accepted

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

countC = (B // C) - (A // C)
countD = (B // D) - (A // D)
def lcm(x, y):
    return (x * y) // frac.gcd(x, y)
lcmCD = lcm(C, D)

countlcm = (B // lcmCD) - (A // lcmCD) 

num = B - A + 1
if A % C == 0:
  countC += 1
if A % D == 0:
  countD += 1
if A % lcmCD == 0:
  countlcm += 1

print(num - countC - countD + countlcm)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

c_m = a // c
c_M = b // c
if a % c != 0:
              c_m += 1

d_m = a // d
d_M = b // d
if a % d != 0:
              d_m += 1

if c > d:
              q = c
              r = d
else:
              q = d
              r = c

while r != 1 and r != 0:
              q_next = r
              r_next = q%r
              q = q_next
              r = r_next          
gcd = 0
if r == 1:
              gcd = 1
if r == 0:
              gcd = q

lcm =(c*d)//gcd
cd_m = a // (lcm)
cd_M = b // (lcm)
if a % ((c*d)//gcd) !=0:
              cd_m += 1

cd_cnt=(cd_M-cd_m+1)

dim = (c_M-c_m+1) + (d_M-d_m+1) - (cd_cnt)
ans = b - a + 1 - dim
print(int(ans))

Submission status: Accepted

Solution code:
import fractions

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

r = A % C
min_c = A if r == 0 else A + C - r
r = A % D
min_d = A if r == 0 else A + D - r
lcm = (C * D) // fractions.gcd(C, D)
r = A % lcm
min_cd = A if r == 0 else A + lcm - r

num_c = max(0, (B - min_c) // C) + (1 if min_c <= B else 0)
num_d = max(0, (B - min_d) // D) + (1 if min_d <= B else 0)
num_cd = max(0, (B - min_cd) // lcm) + (1 if min_cd <= B else 0)
#print(min_c, min_d, min_cd, num_c, num_d, num_cd)
print(B - A + 1 - (num_c + num_d - num_cd))

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
a,b,c,d=map(int,input().split())
def count(start, end, x):
    return (end // x) - (start // x + (1 if start % x else 0)) + 1
print(b-a+1-(count(a,b,c) + count(a,b,d) - count(a,b,c*d//gcd(c,d))))

Submission status: Accepted

Solution code:
import fractions

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

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

A_div_byCorD = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
B_div_byCorD = B//C + B//D - B//lcm(C, D)
#print(A_div_byCorD)
#print(B_div_byCorD)
canbedivided = B_div_byCorD - A_div_byCorD

print(B-A+1 - canbedivided)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)
A, B, C, D = map( int, input().split())
CD = C*D//gcd(C,D)
print(B-A+1 - (B//C - (A-1)//C) - (B//D-(A-1)//D) + (B//CD - (A-1)//CD))

Submission status: Accepted

Solution code:
a, b, c, d = 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(a, b):
    return a * b // gcd(a, b)
def solve(n):
    return n - n//c - n//d + n//lcm(c, d)

div_a = solve(a-1)
div_b = solve(b)
print(div_b - div_a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd
A, B, C, D = list(map(int, input().split()))

def nev(u, C, D):
  l = C*D//gcd(C, D)
  ret = (l-(l//C+l//D)+1)*(u//l)
  m = u % l
  ret += m-(m//C+m//D)
  return ret

a = nev(B, C, D)
a -= nev(A-1, C, D) if A>1 else 0
print(a)

Submission status: Accepted

Solution code:
A,B,C,D=map(int, input().split())
L=D
M=C
if M < L:
    M, L = L, M
while M % L != 0:
    M, L = L, M % L
K=L
E=int((C*D)//K)
F=int(A//E)
G=int(B//E)
H=int(E//C+E//D-1)
I=int((E*(F+1)-A)//C+(E*(F+1)-A)//D)
J=int((B-(E*G))//C+(B-(E*G))//D)
if A%C==0 and A%D==0:
    print(B-A-((G-F-1)*H+I+J-1))
else:
    print(B-A-((G-F-1)*H+I+J))

Submission status: Accepted

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

Submission status: Accepted

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

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

A,B,C,D = (int(x) for x in input().split())
lcmCD = lcm(C, D)
A -= 1
ans = B - A
anstmp = B // C
anstmp -= A // C
ans -= anstmp
anstmp = B // D
anstmp -= A // D
ans -= anstmp
anstmp = B // lcmCD
anstmp -= A // lcmCD
ans += anstmp
print('%d' % ans)

Submission status: Accepted

Solution code:
import fractions

A,B,C,D = input().strip().split(" ")
A = int(A)
B = int(B)
C = int(C)
D = int(D)
X = C*D // fractions.gcd(C,D)

c = B//C - A//C + int(A%C == 0)
d = B//D - A//D + int(A%D == 0)
cd = B//X - A//X + int(A%X == 0)

delim = c + d - cd
result = B - A + 1 - delim 
print(result)

Submission status: Accepted

Solution code:
from fractions import gcd

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

c = (B // C) - (A // C) + int(A % C == 0)
d = (B // D) - (A // D) + int(A % D == 0)
lcm_cd = (C * D) // gcd(C, D)
cd = (B // (lcm_cd)) - (A // (lcm_cd)) + int(A % (lcm_cd) == 0)

c_or_d = c + d - cd

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""解説
B以下の整数のうち、CでもDでも割り切れないものの個数をCountBとする
A以下の整数のうち、CでもDでも割り切れないものの個数をCountAとする

求める答えは、CountB - CountA

・CountBの求め方
B以下の整数のうち、Cで割り切れるものの個数はCountB_C = B//C
B以下の整数のうち、Dで割り切れるものの個数はCountB_D = B//D
B以下の整数のうち、CでもDでも割り切れるものの個数はCountB_CD = B//lcm(C,D)

CountB = B - (CountB_C + CountB_D - CountB_CD)

"""
from fractions import gcd
from math import floor

def solve():
    A, B, C, D = list(map(int, input().split()))
    def lcm(a, b):
        """ aとbの最小公倍数を返す """
        return a*b // gcd(a, b)

    def f(x):
        """ 1以上x以下の整数のうち、CでもDでも割り切れないものの個数を返す """
        #return x - (floor(x/C) + floor(x/D) - floor(x/lcm(C,D)))
        return x - (x//C + x//D - x//lcm(C,D))

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

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""解説
B以下の整数のうち、CでもDでも割り切れないものの個数をCountBとする
A以下の整数のうち、CでもDでも割り切れないものの個数をCountAとする

求める答えは、CountB - CountA

・CountBの求め方
B以下の整数のうち、Cで割り切れるものの個数はCountB_C = B//C
B以下の整数のうち、Dで割り切れるものの個数はCountB_D = B//D
B以下の整数のうち、CでもDでも割り切れるものの個数はCountB_CD = B//lcm(C,D)

CountB = B - (CountB_C + CountB_D - CountB_CD)

"""
from fractions import gcd

def solve():
    A, B, C, D = list(map(int, input().split()))
    def lcm(a, b):
        """ aとbの最小公倍数を返す """
        return a*b // gcd(a, b)

    def f(x):
        """ 1以上x以下の整数のうち、CでもDでも割り切れないものの個数を返す """
        return x - (x//C + x//D - x//lcm(C,D))    

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

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
A,B,C,D = map(int,input().split())
X = max(C,D)
Y = min(C,D)
def gcd(a,b):
  while b!= 0:
    a,b = b,a%b
  return a
l = int(C*D/ gcd(X,Y))
def f(x):
  return x - (x//C + x//D - x//l)
ans = f(B) - f(A-1)
print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

a,b,c,d=map(int, input().split())
tisai = int(c*d/gcd(c,d))
n=[c,d]
count=0
for k in range(2):
    count += ((b//n[k])-((a-1)//n[k]))
count -= ((b//tisai)-((a-1)//tisai))
print(int((b-a+1)-count))

Submission status: Accepted

Solution code:
import sys

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


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


def main():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    E = lcm(C, D)

    total = B - (A-1)
    mul_c = B // C - (A-1) // C
    mul_d = B // D - (A-1) // D
    mul_e = B // E - (A-1) // E
    return total - (mul_c + mul_d - mul_e)


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

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d=map(int,input().split())
lcm=c*d//gcd(c,d)
nc=b//c-a//c
nd=b//d-a//d
nlcm=b//lcm-a//lcm
if a%c==0:
  nc+=1
if a%d==0:
  nd+=1
if a%lcm==0:
    nlcm+=1
print(b-a+1-nc-nd+nlcm)

Submission status: Accepted

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

X = max(C, D)
Y = min(C, D)
remainder = 1
while(remainder != 0):
	remainder = X % Y
	X = Y
	Y = remainder
lcmCD = C * D // X

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

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

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

CD_lcm = int((C * D) / gcd(C, D))
# B以下の数字に関する個数
BCcan = B//C
BDcan = B//D
BCDcan = B//CD_lcm

A1Ccan = (A-1)//C
A1Dcan = (A-1)//D
A1CDcan = (A-1)//CD_lcm

count = (BCcan+BDcan - BCDcan) - (A1Ccan+A1Dcan - A1CDcan)

print(int(B-(A-1) - count))

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)

def calc(n):
    return n-n//C-n//D+n//(lcm(C,D))
 
print(calc(B)-calc(A-1))

Submission status: Accepted

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

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

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

def ans(n, x, y):
    return n - n // c - n // d + n // lcm(x, y)

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

Submission status: Accepted

Solution code:
def s(c,d):
    x = c%d
    if x==0:
        return d
    
    else:
        return s(d,x)

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

Submission status: Accepted

Solution code:
from sys import exit
import fractions

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

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

c_sum = B // C - (A - 1) // C
d_sum = B // D - (A - 1) // D
cd_sum = B // CD - (A - 1) // CD

print(B - A + 1 - (c_sum + d_sum - cd_sum))

Submission status: Accepted

Solution code:
def lcm(a, b):
    if b > a:
        a, b = b, a

    x = a * b
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b

    return x // b


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

n = (B // C) + (B // D) - (B // CD)
n -= (A // C) + (A // D) - (A // CD)
print(B - A - n)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=list(map(int, input().split()))
lcm=int(c*d/fractions.gcd(c,d))
could_divide=(b//c-(a-1)//c) + (b//d-(a-1)//d) - (b//lcm-(a-1)//lcm)
#print("could divide by "+str(c)+" : "+str(b//c-(a-1)//c))
#print("could divide by "+str(d)+" : "+str(b//d-(a-1)//d))
print(b-a+1-could_divide)