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:
a,b,c,d=map(int,input().split())
import fractions
lcm=c*d//fractions .gcd(c,d)
C=b//c-(a-1)//c
D=b//d-(a-1)//d
CD=b//lcm-(a-1)//lcm
al=b-a+1
print(al-C-D+CD)

Submission status: Accepted

Solution code:
A, B, C, D = map(int,(input().split()))
from decimal import Decimal as d
import fractions
cd = C * D / d(fractions.gcd(C, D))

# B-A+1 - (B//C - A//C) - (B//D - A//D) + (B//cd - A//cd)

if (A % C == 0 and A % D != 0) or (A % C != 0 and A % D == 0):
    print(B-A+1 - (B//C - A//C + 1) - (B//D - A//D) + (B//cd - A//cd))
elif A % cd == 0:
    print(B-A+1 - (B//C - A//C + 1) - (B//D - A//D + 1) + (B//cd - A//cd + 1))
else:
    print(B-A+1 - (B//C - A//C) - (B//D - A//D) + (B//cd - A//cd))

Submission status: Accepted

Solution code:
from fractions import gcd

l, r, x, y = map(int, input().split())
lcm = int(x * y / gcd(x, y))

xn = r // x - (l - 1) // x
yn = r // y - (l - 1) // y
xyn = r // lcm - (l - 1) // lcm
ans = int(r - l + 1 - xn - yn + xyn)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
e = b//c - (a-1)//c
f = b//d - (a-1)//d
def lcm(x, y):
	return (x * y) // gcd(x, y)
g = lcm(c, d)
h = b//g - (a-1)//g

print (b-a+1 -(e+f-h))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

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

def f(n, a, b):
    return n - (n // a + n // b - n // (lcm(a, b)))

def main():
    ans = f(b, c, d) - f(a-1, c, d)
    return ans

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = (int(abcd) for abcd in input().split())
lcm_CD = C*D // fractions.gcd(C, D)
in_B = B - ((B//C + B//D) - B//lcm_CD)
in_under_A = (A-1) - (((A-1)//C + (A-1)//D) - (A-1)//lcm_CD)
print(in_B - in_under_A)

Submission status: Accepted

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

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

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

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

a = B//C-(A-1)//C
b = B//D-(A-1)//D
c = B//E-(A-1)//E
print(B-A+1-a-b+c)

Submission status: Accepted

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


def ea(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x %= y
        x, y = y, x
    return y


gcd = ea(C, D)

ans = B - A + 1
ans -= B // C - (A - 1) // C
ans -= B // D - (A - 1) // D
ans += B // ((C * D) // gcd) - (A - 1) // ((C * D) // gcd)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def num(a,x):
  return (a-(a%x))//x

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
a,b,c,d = map(int,input().split())	
def my_gcd(i,j):
    if i > j: i,j = j,i
    while i != 0:
        if j % i != 0:
            i,j = j%i,i
        else: return i
def not_div(n):
    return b//n  - (a-1) //n
print(not_div(1)-not_div(c)-not_div(d)+not_div(c*d//my_gcd(c,d)))

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
def gcd(n,m):
    n,m=sorted([n,m])
    while(m%n!=0):
        n,m=m%n,n
    return n
def lcm(n,m):
    return n*m//gcd(n,m)
cd=lcm(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())

p, q = c, d
while q:
  p, q = q, p % q
e = c * d // p

div_c = b // c - (a-1) // c
div_d = b // d - (a-1) // d
div_e = b // e - (a-1) // e

print(b - a + 1 - div_c - div_d + div_e)

Submission status: Accepted

Solution code:
import fractions

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

c_count = b//c - (a-1)//c
d_count = b//d - (a-1)//d
cd_count = b//(c*d//fractions.gcd(c,d)) - (a-1)//(c*d//fractions.gcd(c,d))

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

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

num = b//c + b//d - b//f
num -= (a-1)//c + (a-1)//d - (a-1)//f

print(b-a+1-num)

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

c = B // C - (A - 1) // C
d = B // D - (A - 1) // D
CD = lcm(C, D)
cd = B // CD - (A - 1) // CD

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

Submission status: Accepted

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

def count_q(a,b,m):
    if a%m==0:
        q = b//m -a//m +1
    else:
        q = b//m - a//m
    return q


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

da = lcm(c,d)

qc = count_q(a,b,c)
qd = count_q(a,b,d)
qe = count_q(a,b,da)
ans = (b-a+1)-(qc+qd-qe)
print(ans)

Submission status: Accepted

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

p=a-((a//c)+(a//d)-(a//y))

q=b-((b//c)+(b//d)-(b//y))

print(int(q-p))

Submission status: Accepted

Solution code:
#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

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

lcm = lcm_base(C, D)

n_c = (B // C) - ((A - 1) // C)
n_d = (B // D) - ((A - 1) // D)
n_cd = (B // lcm) - ((A - 1) // lcm)

ans = (B - A + 1) - n_c - n_d + n_cd
print(ans)

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)

def ans_cnt(i,y,z):
    return i - (i//y + i//z - i//lcm(y,z))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
def div_cnt(x):
    return b//x-(a-1)//x

a,b,c,d = map(int,input().split())
e = c*d//fractions.gcd(c,d)
cnt = b-a+1
c_cnt = div_cnt(c)
d_cnt = div_cnt(d)
e_cnt = div_cnt(e)
print(cnt-c_cnt-d_cnt+e_cnt)

Submission status: Accepted

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

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

a_c = (a-1)//c
a_d = (a-1)//d
a_cd = (a-1)//(c*d//gcd(c,d))

b_c = b//c
b_d = b//d
b_cd = b//(c*d//gcd(c,d))

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

print(bb - aa)

Submission status: Accepted

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

x = (c*d)//fractions.gcd(c,d)
A = (a-1) - (a-1)//c - (a-1)//d + (a-1)//x
B = b - b//c - b//d + b//x
print(int(B-A))

Submission status: Accepted

Solution code:
"""
「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では
(B 以下の整数のうちの〜を満たすものの個数) から
(A-1 以下の整数のうちの〜を満たすものの個数) を引く

- (全体)
+ (C の倍数の個数)
+ (D の倍数の個数)
- (C の倍数でも D の倍数でもあるものの個数)
"""

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

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
  
def u(n,C,D):
  return int(n - n//C - n//D + n//(C//gcd(C,D)*D))

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

Submission status: Accepted

Solution code:
import math


def gcd(x, y):
    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())
ALL = b - a +1
G = lcm(c, d)
num = math.floor(b // c) - math.floor((a-1) // c) + math.floor(b // d) - math.floor((a-1) // d) - (math.floor(b // G) - math.floor((a-1) // G))
print(ALL - num)

Submission status: Accepted

Solution code:
# 1時間位はかかった
# lcmはfloatで返され、floatのまま処理を続けると値が正確でなくなる点になかなか気づけなかった

import fractions

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

Submission status: Accepted

Solution code:
import fractions

a,b,c,d = map(int, input().split())
#print(a,b,c,d)
total = b-a+1
#print(total)
lcm = int(c*d / fractions.gcd(c,d))
#print(lcm)
x = (b//c) + (b//d) - (b//lcm)
y = ((a-1)//c) + ((a-1)//d) - ((a-1)//lcm)
#print(x,y)
print(total - (x - y))

Submission status: Accepted

Solution code:
import fractions

def main():
    a, b, c, d = map(int, input().split())
    l =  (c * d) // fractions.gcd(c, d)
    cntb = b - (b // c + b // d - b // l)
    cnta = (a-1) - ((a-1) // c + (a-1) // d - (a-1) // l)
    ans = cntb - cnta

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(n,m):#n,mは正の整数、最大公約数
    if n%m==0:
        return m
    elif m%n==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

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

lcm=C*D//gcd(C,D)
a=[0]*3
b=[0]*3
a[0]=(A-1)//C #A-1以下のCの倍数の個数
a[1]=(A-1)//D
a[2]=(A-1)//lcm
b[0]=B//C
b[1]=B//D
b[2]=B//lcm

print(B-A+1-((b[0]-a[0])+(b[1]-a[1])-(b[2]-a[2])))

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

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

n = b - a + 1
n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
n_cd = b//lcm(c,d) - (a-1)//lcm(c,d)

print(n - n_c - n_d + n_cd)

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

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

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

Submission status: Accepted

Solution code:
def gcd(c, d):
  if c <= d:
    c, d = d, c
  while c % d:
    c, d = d, c % d
  return d
def lcm(c, d):
  return (c * d) // gcd(c, d)

A, B, C, D = map(int, input().split())
c_or_d = ((B // C) - ((A - 1) // C)) + ((B // D) - ((A - 1) // D)) - ((B // lcm(C, D)) - ((A - 1) // lcm(C, D)))
print(B - A + 1 - c_or_d)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
BdivC, BdivD = B // C, B // D
AdivC, AdivD = (A - 1) // C, (A - 1) // D
GCD = gcd(C, D)
BdivCD, AdivCD = B // ((C * D) // GCD), (A - 1) // ((C * D) // GCD)
N1 = BdivC + BdivD - BdivCD
N2 = AdivC + AdivD - AdivCD
ans = (B - (A - 1)) - (N1 - N2)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = map(int, input().split())
BdivC, BdivD = B // C, B // D
AdivC, AdivD = A // C, A // D
GCD = gcd(C, D)
BdivCD, AdivCD = B // ((C * D) // GCD), A // ((C * D) // GCD)
N1 = BdivC + BdivD - BdivCD
N2 = AdivC + AdivD - AdivCD
ans = (B - A) - (N1 - N2)
if(A % C != 0): ans += 1
print(ans)

Submission status: Accepted

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


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


def search(n, i, j):
    l = lcm(i, j)
    return n - n // i - n // j + n // l


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

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)
la = a // l
lb = b // l
aa = a // c + a // d - la
bb = b // c + b // d - lb


print((b - a) - (bb - aa))

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

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

b_c = b - b // c
b_d = b - b // d
b_cd = b - b // lcm
z_to_b = b_c + b_d - b_cd

am1 = a-1
a_c = am1 - am1 // c
a_d = am1 - am1 // d
a_cd = am1 - am1 // lcm
z_to_a = a_c + a_d - a_cd

print(z_to_b - z_to_a)

Submission status: Accepted

Solution code:
import math
import fractions

def main(a,b,c,d):
    count = 0
    for i in range(a, b+1):
        if i%c != 0:
            if i%d != 0:
                count += 1

    return count

def main2(a,b,c,d):
    g = (c * d) // fractions.gcd(c,d)
    tempC = (b // c) - ((a-1) // c)
    tempD = (b // d) - ((a-1) // d)
    tempCD = (b // g) - ((a-1) // g)
    return (b - (a-1)) - (tempC + tempD - tempCD)

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

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = [int(x) for x in input().split()]

def div(x, y, z):
    return x - (x // y) - (x // z) + (x // (y * z // gcd(y, z)))

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

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

Submission status: Accepted

Solution code:
import fractions
def main(A,B,C,D):
    allAB = B - A + 1
    divC = B // C - (A-1) // C
    divD = B // D - (A-1) // D
    lcmCD = lcm(C,D)
    divCD = B // (lcmCD) - (A-1) // (lcmCD)
    count = allAB - divC - divD + divCD
    return count

def lcm(x, y):
    return (x*y) // fractions.gcd(x,y)
    
A,B,C,D = map(int, input().split())
print(main(A,B,C,D))

Submission status: Accepted

Solution code:
from fractions import gcd

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

def f(X):
  return X-X/C-X/D+X/(C*D/gcd(C,D))
print f(B)-f(A-1)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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


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


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


A, B, C, D = map(int, input().split())
ans_b = B - (B // C) - (B // D) + (B // lcm_base(C, D))
ans_a = (A - 1) - ((A - 1) // C) - ((A - 1) // D) + ((A - 1) // lcm_base(C, D))
print(ans_b - ans_a)

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
def quo_items(x, num1, num2):
    num1_quo = x // num1
    num2_quo = x // num2
    num12_quo = x // int((num1 / gcd(num1, num2) * num2))
    items = x - num1_quo - num2_quo + num12_quo
    return items

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

Submission status: Accepted

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

A, B, C, D = map(int, input().split())
lcm = (C * D) // gcd(C, D)
bsum = B - (B//C) - (B//D) + (B//lcm)
asum = (A - 1) - ((A - 1) // C) - ((A - 1) // D) + ((A - 1) // lcm)

print(bsum-asum)

Submission status: Accepted

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

Submission status: Accepted

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

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


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:
import fractions
A, B, C, D = map(int, input().split())
M = C * D // fractions.gcd(C, D)
def f(x):
  N = x - x//C - x//D + x//M 
  return N
print(f(B) - f(A-1))

Submission status: Accepted

Solution code:
import fractions

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

U = B - A + 1

x = B // C - (A-1) // C
y = B // D - (A-1) // D

lcm = C*D // fractions.gcd(C,D)
z = B // lcm - (A-1) // lcm

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

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
min = min(C, D)
max = max(C, D)
 
def gcd(max, min):
  while min:
    max, min = min, max%min
  return max
lcm = max*min//gcd(max,min)

#Cで割り切れる数
c = B//C-(-(-A//C))+1
#Dで割り切れる数
d = B//D-(-(-A//D))+1
#CとDで割り切れる数
e = B//lcm-(-(-A//lcm))+1

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

Submission status: Accepted

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

cZ = (b//c)-((a-1)//c)

dZ = (b//d)-((a-1)//d)

cdZ = (b//(lcm(c,d)))-((a-1)//(lcm(c,d)))

ans = b-a+1-cZ-dZ+cdZ
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

    ans = 0

    bc = b // c
    bd = b // d
    cd = lcm(c,d)
    bcd = b // cd

    bcount = b - bc -bd + bcd

    ac = (a-1) // c
    ad = (a-1) // d
    acd = (a-1) //cd

    acount = (a-1) - ac -ad + acd

    print(bcount-acount)

if __name__ == '__main__':
    main()

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 yakusuu(c, d, n):
  return (n // c) + (n // d) - (n // lcm(c, d))

def yakusuu_igai(c, d, n):
  return n - yakusuu(c, d, n)

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

Submission status: Accepted

Solution code:
import fractions

x = input().split(" ")
a = int(x[0])
b = int(x[1])
c = int(x[2])
d = int(x[3])

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

cd = c*d // fractions.gcd(c,d)
cd_count = (b//cd) - ((a-1)//cd)
ans = (b+1-a)-c_count-d_count+cd_count

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import fractions

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

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

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

s = a + b - c

ans = B - (A-1) - s

print(ans)

Submission status: Accepted

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

def gcd(x,y):
  while y:
    x, y = y, x%y
  return x
lcm = c*d // gcd(c,d)

cnt = lambda z: z - z//c - z//d + z//lcm
print(cnt(b)-cnt(a-1))

Submission status: Accepted

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

def gcd(x,y):
  while y:
    x, y = y, x%y
  return x
lcm = c*d // gcd(c,d)

def cnt(z):
  return b//z - (a-1)//z

print(b+1-a-cnt(c)-cnt(d)+cnt(lcm))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def euclidian(a, b): #ユークリッドの互除法
    
    tmp = max(a,b)
    b = min(a,b)
    a = tmp

    mod = 1
    
    while (mod > 0):
        mod = a % b
        a, b = b, mod
    
    return(a)

low, high, C, D = map(int, input().split())

common = C * D // euclidian(C, D)
right_count = high - (high // C + high // D) + high // common 
l_tmp = low - 1
left_count = l_tmp - (l_tmp // C + l_tmp // D) + l_tmp // common

answer = right_count - left_count
print(int(answer))

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
 
def gcd(x, y):
    if y > x:
        return gcd(y, x)
    if x % y == 0:
        return y
    return gcd(y, x%y)
 
cd = c * d // gcd(c, d)
 
b_div = b - b//c - b//d + b//cd
a_div = a-1 - (a-1)//c - (a-1)//d + (a-1)//cd
 
print(b_div - a_div)

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
 
def gcd(x, y):
    if y > x:
      return gcd(y, x)
    if x % y == 0:
        return y
    return gcd(y, x%y)
 
cd = c // gcd(c,d) * d
 
a -= 1
a_ = a - a//c - a//d + a//cd
b_ = b - b//c - b//d + b//cd
 
print(b_ - a_)

Submission status: Accepted

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

a -= 1
a_ = a - a//c - a//d + a//cd
b_ = b - b//c - b//d + b//cd
 
print(b_ - a_)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

def main():
    A,B,C,D = cin.mapInt()
    A -= 1
    S = B // C + B // D - B // Math.lcm(C,D)
    T = A // C + A // D - A // Math.lcm(C,D)
    print(B - S - (A - T))
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def sa(c,d):
    
    if c>d:
        nn=c//d
        c2=c-d*nn
        if c2<d:
            return c2,d
        else:
            return d,c2
    else :
        nn=d//c
        c2=d-c*nn
        if c2<c:
            return c2,c
        else:
            return c,c2

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

mp=c*d

c1=c
d1=d
for i in range(10**18):
    c2,d2=sa(c1,d1)
#    print("c1,d1,c2,d2",c1,d1,c2,d2)    
    if c2<=0:
        break
    c1=c2
    d1=d2

mcm=int(mp/c1)

ac2=(a-1)//c
ad2=(a-1)//d
am2=(a-1)//mcm

bc2=b//c
bd2=b//d
bm2=b//mcm
#print(mcm,ac2,bc2,ad2,bd2,am2,bm2)     

icnt=(bc2-ac2)+(bd2-ad2)-(bm2-am2)
icnt=(b+1-a)-icnt

print(icnt)

Submission status: Accepted

Solution code:
def sa(c,d):
    
    if c>d:
        nn=int(c/d)
        c2=c-d*nn
        if c2<d:
            return c2,d
        else:
            return d,c2
    else :
        nn=int(d/c)
        c2=d-c*nn
        if c2<c:
            return c2,c
        else:
            return c,c2

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

mp=c*d

c1=c+1-1
d1=d+1-1
for i in range(10**18):
    c2,d2=sa(c1,d1)
#    print("c1,d1,c2,d2",c1,d1,c2,d2)    
    if c2<=0:
        break
    c1=c2
    d1=d2

mcm=int(mp/c1)

ac2=int(int(a-1)//int(c))
ad2=int(int((a-1))//int(d))
am2=int(int((a-1))//mcm)

bc2=int(int(b)//int(c))
bd2=int(int(b)//int(d))
bm2=int(int(b)//mcm)
#print(mcm,ac2,bc2,ad2,bd2,am2,bm2)     

icnt=(bc2-ac2)+(bd2-ad2)-(bm2-am2)
icnt=(b+1-a)-icnt

print(icnt)

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


# import re
# import array
# import copy
# import functools
# import operator

# import math
# import string
import fractions
# from fractions import Fraction
from fractions import gcd

# import collections
# import itertools
# import bisect

# import heapq
# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace
# from queue import PriorityQueue as pq
from queue import Queue

# from itertools import accumulate

# from collections import deque
# from collections import Counter

from operator import mul
from functools import reduce

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


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


# import random
# import time

a, b, c, d = map(int, input().strip().split())
n = b - a  + 1
m1 = b // c - (a - 1) // c
m2 = b // d - (a - 1) // d
m3 = b // lcm(c, d) - (a - 1) // lcm(c, d)
ans = n - (m1 + m2 - m3)
print(ans)

Submission status: Accepted

Solution code:
#python3
from fractions import gcd

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


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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

p = count(a-1)
q = count(b)
print((b - a + 1) - (q - p))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
def calc(n,x,y):
    cnt = n // x
    cnt += n//y
    lcm = x*y//fractions.gcd(x,y)
    cnt -= n//lcm
    return n - cnt

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

Submission status: Accepted

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


def calc(n, div_1, div_2):
    cnt = n // div_1
    cnt += n // div_2
    lcm = div_1 * div_2 // gcd(div_1, div_2)
    cnt -= int(n // lcm)
    return n - cnt


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 calc(n, x, y):
    z = lcm(x, y)
    return n // x + n // y - n // z


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

Submission status: Accepted

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

def count_q(a, b, m):

    if a % m == 0:
        q = b // m  - a // m + 1
    else:
        q = b // m - a // m
    return q

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

lcm = lcm(C, D)
qc = count_q(A, B, C)
qd = count_q(A, B, D)
qcd = count_q(A, B, lcm)

ans = (B - A + 1) - (qc + qd - qcd)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

cnt_c = B//C - (A-1)//C
cnt_d = B//D - (A-1)//D

lcm = C * D // gcd(C, D)
cnt_cd = B//lcm - (A-1)//lcm

divisible = cnt_c + cnt_d - cnt_cd
print(B-A+1-divisible)

Submission status: Accepted

Solution code:
from math import ceil, floor
from fractions import gcd

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

def div_count(n, p, q):
  lcm = p*q // gcd(p, q)
  return n - n//p - n//q + n//lcm

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

Submission status: Accepted

Solution code:
from fractions import gcd

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


def division(x, p, q):
    return x - x // p - x // q + x // (p * q // gcd(p, q))


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

Submission status: Accepted

Solution code:
def main():
    def gcd(a,b):
        while b!=0:
            a,b=b,a%b
        return a
    def lcm(a, b):
        return (a * b)//gcd(a,b)
    def ans(N,C,D):
        return N-N//C-N//D+N//lcm(C,D)

    A,B,C,D = map(int,input().split())
    print(ans(B,C,D)-ans(A-1,C,D))
    
if __name__=="__main__":
    main()

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:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


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


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


A, B, C, D = [int(i) for i in input().split()]
c_ho = ho(A, B, C)
d_ho = ho(A, B, D)
cd_ho = ho(A, B, lcm(C, D))
print(B - A + 1 - (c_ho + d_ho) + cd_ho)

Submission status: Accepted

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

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

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

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

c_ho=ho(a,b,c)
d_ho=ho(a,b,d)
cd_ho=ho(a,b,lcm(c,d))

print(b-a+1-(c_ho+d_ho)+cd_ho)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import fractions

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

n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
#print("n_c: ", n_c)
#print("n_d: ", n_d)

cd = c*d//fractions.gcd(c,d)
n_cd = b//cd - (a-1)//cd
#print("n_cd: ", n_cd)

n_ab = b+1-a
#print("n_ab: ", n_ab)

print(n_ab-(n_c+n_d)+n_cd)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

    if c == 1 or d == 1:
        print(0)
        return
    g = lcm(c,d)
    cmod = b//c - (a-1)//c
    dmod = b//d - (a-1)//d
    cdmod = b//g - (a-1)//g
    print(b-a+1-cmod-dmod+cdmod)
    
if __name__ == '__main__':
    main()