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:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys
from pprint import pprint
import itertools
import fractions

A, B, C, D = [ int(x) for x in input().split() ]
#B = [ int(x) for x in input().split() ]
lcm = int(C * D // fractions.gcd(C, D))

def not_devide_num(n):
    return n - (n // C + n // D - n // lcm)

print (not_devide_num(B) - not_devide_num(A - 1))

Submission status: Accepted

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

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

def g(a, b):
    return a * b // f(a,b)

def h(x, a, b):
    return x - (x // a) - (x // b) + (x // g(a,b))

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

def lcm(x,y):
    return x*y//gcd(x,y)
ab = b-a+1
a= a-1
cd = lcm(c,d)
a_count = (a//c)+(a//d)-(a//cd)
b_count = (b//c)+(b//d)-(b//cd)

print(ab-(b_count-a_count))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

print(n - (c + d - cd))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
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 = m()

kk = -(-a//c)

kkk = b//c

ll = -(-a//d)

lll = b//d

p = lcm(c,d)

pp = -(-a//p)

ppp = b//p
print(b-a+1-(kkk-kk+1)-(lll-ll+1)+(ppp-pp+1))

Submission status: Accepted

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

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


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


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


lcm_cd = lcm(c, d)

div_cd = b // lcm_cd - (a - 1) // lcm_cd

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

Submission status: Accepted

Solution code:
from math import sqrt, factorial
from fractions import gcd
from sys import setrecursionlimit
from itertools import product
from string import ascii_lowercase as abc
setrecursionlimit(10000000)

def inpl(): return list(map(int, input().split()))
A, B, C, D = inpl()
E = C*D//gcd(C, D)
X = B//C - (A-1)//C
Y = B//D - (A-1)//D
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)

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

E = lcm(C,D)

print(B - B // C - B // D + B // E - (A - A // C - A // D + A // E))

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())
c_div = max(B // C - ((A+C-1) // C) + 1, 0)
d_div = max(B // D - ((A+D-1) // D) + 1, 0)
cd_div = max(B // lcm(C, D) - ((A+lcm(C, D)-1) // lcm(C, D)) + 1, 0)
ans = B - A + 1 - c_div - d_div + cd_div
print(ans)

Submission status: Accepted

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

def solve(A: int, B: int, C: int, D: int):
    E = C * D // fractions.gcd(C, D)
    count_c = B // C - (A-1) // C
    count_d = B // D - (A-1) // D
    count_e = B // E - (A-1) // E
    print(B-A+1 - count_c - count_d + count_e)
    return


# 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
    solve(A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def gcd(m, n) :
    r = m % n
    while r != 0 :
        m, n = n, r
        r = m % n
    return n

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

C1 = (A - 1) // C
C2 = B // C
D1 = (A - 1) // D
D2 = B // D
CD1 = (A - 1) // CD
CD2 = B // CD

print(B - A + 1 - (C2 - C1 + D2 - D1 - (CD2 - CD1)))

Submission status: Accepted

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

Submission status: Accepted

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


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


num_mul_C = B // C - A // C + (A % C == 0)
num_mul_D = B // D - A // D + (A % D == 0)

lcm = C * D // gcd(C, D)
num_mul_lcm = B // lcm - A // lcm + (A % lcm == 0)
print(B - A + 1 - (num_mul_C + num_mul_D - num_mul_lcm))

Submission status: Accepted

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

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

A_C = (A-1) // C
B_C = B // C
A_D = (A-1) // D
B_D = B // D
A_CD = (A-1) // CD
B_CD = B //CD

ans =(B-A+1) - ((B_C - A_C) + (B_D - A_D) - (B_CD - A_CD))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import accumulate
import sys
sys.setrecursionlimit(10**6)
mo=10**9+7

def gcd(x,y):
    if x%y==0:
        return y
    while x%y!=0:
        x,y=y,x%y
    return y
        
#n=int(input())  
a,b,c,d=map(int,input().split())
#a=[int(i) for i in input().split()]
#a=[l+i-1 for i in range(1,n+1)]
def f(n,k):
    return n//k

def f2(a):
    #print(a,c,d,'|',f(a,c),f(a,d),f(a,c*d//gcd(c,d)))
    return a-f(a,c)-f(a,d)+f(a,c*d//gcd(c,d))
    

ans=f2(b)-f2(a-1)
print(ans)#,f2(b),f2(a-1))

Submission status: Accepted

Solution code:
from sys import stdin
import fractions

A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]


def div(n, x, y):
    lcs = int(x * y / fractions.gcd(x, y))
    return n - int(n // x) - int(n // y) + int(n // lcs)


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

Submission status: Accepted

Solution code:
import fractions
gcd = fractions.gcd

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

CD =  C* D // gcd(C, D)
def calc(X):
    num_c = X // C
    num_d = X // D
    num_cd = X // CD
    ret = num_c + num_d - num_cd
    return ret

o1 = calc(B)
o2 = calc(A-1)
#print(o1, o2)
o = o1 - o2
out = B - A + 1 - o
print(out)

Submission status: Accepted

Solution code:
from math import factorial
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())

upper=b//c+b//d-b//lcm(c,d)
lower=(a-1)//c+(a-1)//d-(a-1)//lcm(c,d)

#print(upper)
#print(lower)
print(b-a+1-(upper-lower))

Submission status: Accepted

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

diff = B - A + 1

num_c = diff // C
if A % C + diff % C > C:
    num_c += 1
num_d = diff // D
if A % D + diff % D > D:
    num_d += 1
cd = C * D // gcd(C, D)
num_cd = diff // cd
if A % cd + diff % cd > cd:
    num_cd += 1

ans = diff - (num_c + num_d - num_cd)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(m, n):
    if m < n:
        return gcd(n, m)
    elif n == 0:
        return m
    return gcd(n, m % n)

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

A, B, C, D = map(int, input().split())
all_nums = B - A + 1
c_divisible = B // C - (A // C if A % C != 0 else A // C - 1) 
d_divisible = B // D - (A // D if A % D != 0 else A // D - 1)
cd_divisible = B // lcm(C, D) - (A // lcm(C, D) if A % lcm(C, D) != 0 else A // lcm(C, D) - 1)
print(all_nums - c_divisible - d_divisible + cd_divisible)

Submission status: Accepted

Solution code:
import fractions

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

b = B//C + B//D - B//((C*D)//fractions.gcd(C, D))

A -= 1
a = A//C + A//D - A//((C*D)//fractions.gcd(C, D))
# print (a, b)
print ((B-b) - (A - a))

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

def wari(n,x,y):
    return n- ( (n//x)+(n//y)-(n//(lcm(x,y))) )

#print(wari(b,c,d))
#print(wari(a-1,c,d))

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

Submission status: Accepted

Solution code:
import fractions


def solve(a,b,c,d):
    a -= 1
    bc = b // c
    bd = b // d
    bcd = b // (c*d//fractions.gcd(c, d))

    ac = a // c
    ad = a // d
    acd = a //  (c*d//fractions.gcd(c, d))

    return b - bc - bd + bcd - (a - ac - ad + acd)
    
if __name__ == "__main__":

    assert solve(4,9,2,3) == 2
    assert solve(10, 40, 6,8) == 23
    assert solve(314159265358979323, 846264338327950288, 419716939, 937510582) == 532105071133627368

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

Submission status: Accepted

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

def f(x, y, z):
    return z // x - (y - 1) // x


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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20

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

def count(L,R,d):
    if L%d == 0:
        left = L
    else:
        left = L - L%d + d
    if R%d ==0:
        right = R
    else:
        right = R - R%d
    v = max((right-left)//d + 1, 0)
    return(v)

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

multiple = count(A,B,C) + count(A,B,D) - count(A,B,lcm)
# print(count(A,B,C) , count(A,B,D) , count(A,B,lcm), lcm)
# print(multiple)
ans = B-A+1 - multiple
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    A, B, C, D = LI()

    Cで割り切れる個数 = B // C - (A-1) // C
    Dで割り切れる個数 = B // D - (A-1) // D
    from fractions import gcd
    def lcm(x, y):
        return x * y // gcd(x, y)
    CDの最小公倍数 = lcm(C,D)
    CでもDでも割り切れる個数 = B // CDの最小公倍数 - (A-1) // CDの最小公倍数

    print(B-(A-1) - Cで割り切れる個数 - Dで割り切れる個数 + CでもDでも割り切れる個数)


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

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

count_C = B//C - (A+C-1)//C + 1
count_D = B//D - (A+D-1)//D + 1

CD = lcm_base(C, D)
countCD = B//CD - (A+CD-1)//CD + 1

ans = (B-A+1) - count_C - count_D + countCD
print(ans)

Submission status: Accepted

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


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

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


ac = a // c
ad = a // d
acd = a // lcm(c, d)

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

bx = b - (bc + bd) + bcd
ax = a - (ac + ad) + acd
print(bx - ax)

Submission status: Accepted

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


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


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


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

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

x = B // C - (A - 1) // C
y = B // D - (A - 1) // D
E = lcm(C, D)
z = B // E - (A - 1) // E
print(B - A + 1 - (x + y - z))

Submission status: Accepted

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

def aaa(a, b):
    return a // b

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


c1 = aaa(A-1, C)
c2 = aaa(B, C)
c = c2 - c1

d1 = aaa(A-1, D)
d2 = aaa(B, D)
d = d2 - d1

cd1 = aaa(A-1, lcm(C, D))
cd2 = aaa(B, lcm(C, D))
cd = cd2 - cd1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def gcd(m, n):
    # 入力を m, n (m ≧ n) とする。
    tmp = max(m,n)
    n = min(m,n)
    m = tmp
    # n = 0 なら、 m を出力してアルゴリズムを終了する。
    if n == 0:
        return m
    # m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。
    return gcd(n, m % n)


a,b,c,d = get_nums_l()

# cで割れる個数
t = a - (a%c-1)
cx = (b-t+1)//c + (1 if a%c==0 else 0)
# dで割れる個数
t = a - (a%d-1)
dx = (b-t+1)//d + (1 if a%d==0 else 0)
# c,dどちらも割れる個数
cd = c*d //(gcd(c,d))
t = a - (a%cd-1)
cdx = (b-t+1)//cd + (1 if a%cd==0 else 0)

all = b-a+1
print(all - cx - dx + cdx)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D = map(int,input().split())
def f(n):
    x = n//C
    y = n//D
    z = n//(C*D//gcd(C,D))
    return n - x - y + z

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

Submission status: Accepted

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

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)

A,B,C,D = (int(i) for i in input().split())

hogeb = B // D
hogec = B // C
hogebc = B // lcm(D,C)

hoge = B-(hogeb + hogec -hogebc)

ononb = (A-1) // D
ononc = (A-1) // C
ononbc = (A-1) // lcm(D,C)

onon = A-1-(ononb + ononc - ononbc)

print(hoge-onon)

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)

g = gcd(c,d)
m = (c//g) * (d//g) * g

dc_a = (a-1)//c
dd_a = (a-1)//d

dc_b = b//c
dd_b = b//d

dm_a = (a-1)//m
dm_b = b//m

res = b-a+1

alll = (dc_b - dc_a) + (dd_b - dd_a) - (dm_b - dm_a)

res = res - alll
print(res)

Submission status: Accepted

Solution code:
from fractions import gcd

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

C_num = B // C - (A - 1) // C
D_num = B // D - (A - 1) // D
CD = (C * D) // gcd(C, D)
CD_num = B // CD - (A - 1) // CD
print(int(B - A + 1 - C_num - D_num + CD_num))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y

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


A,B,C,D=LI()

Cnum = B//C - A//C + (not A % C)
Dnum = B//D - A//D + (not A % D)
# print(Cnum)
# print(Dnum)
LC = lcm(C,D)
LCnum = B//LC - A//LC + (not A % LC)

BAISUU = ((Cnum + Dnum) - LCnum)
print((B-A+1) - ((Cnum + Dnum) - LCnum))

Submission status: Accepted

Solution code:
import fractions

A,B,C,D=map(int,input().split())
#Cの約数の個数
C_only=(B//C)-((A-1)//C)
#Dの約数の個数
D_only=(B//D)-((A-1)//D)
#C_Dの最小公倍数
C_D=(C*D)//fractions.gcd(C,D)
C_D_both=(B//C_D)-((A-1)//C_D)

print(B-A+1-C_only-D_only+C_D_both)

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


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


E = lcm(C, D)

res_b = B // C + B // D - B // E
res_a = (A - 1) // C + (A - 1) // D - (A - 1) // E

print((B - res_b) - (A - 1 - res_a))

Submission status: Accepted

Solution code:
import fractions

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

A, B, C, D = list(map(int, input().split()))
NC = B // C - A // C
if A % C == 0:
  NC += 1
ND = B // D - A // D
if A % D == 0:
  ND += 1
LCM = lcm(C, D)
NCA = B // LCM - A // LCM
if A % LCM == 0:
  NCA += 1
TOTAL = B - A + 1
NOTN = NC+ND-NCA
print (TOTAL - NOTN)

Submission status: Accepted

Solution code:
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 = map(int,input().split())
l = lcm(c,d)
ans = b-a+1
ans-=b//c
ans-=b//d
ans+=b//l
ans+=(a-1)//c
ans+=(a-1)//d
ans-=(a-1)//l
print(ans)

Submission status: Accepted

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

def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

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

E = lcm(C, D)

def div(X):
  return X - ((X // C) + (X // D)) + (X // E)

print(div(B) - div(A - 1))

Submission status: Accepted

Solution code:
def gcd(x,y):
    while not y == 0:
        x,y = y,x%y
    return x  
A,B,C,D = map(int,input().split())
A -= 1
ans = (B-(B//C)-(B//D)+(B//(C*D//gcd(C,D))))-(A-(A//C)-(A//D)+(A//(C*D//gcd(C,D))))
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
    while x%y!=0:
        x,y=y,x%y
    return y

#print(gcd(C,D))
ANS=0
ANS+=(B//C)
#print(ANS)
ANS-=((A-1)//C)
#(ANS)
ANS+=(B//D)
#print(ANS)
ANS-=((A-1)//D)
#print(ANS)
ANS-=(B//(C*D//gcd(C,D)))
ANS+=((A-1)//(C*D//gcd(C,D)))
#print(C*D//gcd(C,D))
print(B-A+1-ANS)

Submission status: Accepted

Solution code:
from fractions import gcd
inpl = lambda: list(map(int,input().split()))
def lcm(a,b): return a*b//gcd(a,b)
A, B, C, D = inpl()
CD = lcm(C,D)
XB = B//C + B//D - B//CD
XA = (A-1)//C + (A-1)//D - (A-1)//CD
X = XB - XA
Z = (B - A + 1) - X
print(Z)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a


def num(l,r,n):
    nr = r//n
    nl = l//n
    if l%n == 0:
        return nr-nl+1
    else:
        return nr-nl
saishou = int(c*d/(gcd(c,d)))
n = b-a+1
n1 = num(a,b,c)
n2 = num(a,b,d)
n3 = num(a,b,saishou)
print(n-(n1+n2-n3))

Submission status: Accepted

Solution code:
##!/usr/bin/env python3
import sys
# from operator import itemgetter
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    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

    # write code
    X = (B // C) - ((A-1) // C)
    Y = (B // D) - ((A - 1) // D)
    Z = (B // (C * D // gcd(C, D))) - ((A - 1) // (C * D // gcd(C, D)))
    print(int(B-A+1-X-Y+Z))

Submission status: Accepted

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

Submission status: Accepted

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

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

    return B-A+1 - ((B//C + B//D - B//E)-((A-1)//C + (A-1)//D - (A-1)//E))

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

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
sb = B // C
sa = (A - 1) // C
tb = B // D
ta = (A - 1) // D


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


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


mb = B // lcm
ma = (A - 1) // lcm

L = sb - sa + tb - ta - (mb - ma)
print(B - A - L + 1)

Submission status: Accepted

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

tmp_minL = b // minL
tmp_c = b // c
tmp_d = b // d


tma_minL = (a - 1) // minL
tma_c = (a - 1) // c
tma_d = (a - 1) // d


left = tmp_c + tmp_d - tmp_minL
right = tma_c + tma_d - tma_minL


print(b - a + 1 - (left - right))

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  
nc=b//c-(a-1)//c
nd=b//d-(a-1)//d
x=c*d//gcd(c,d)
ncd=b//x-(a-1)//x
#print(nc,nd,x,ncd)
print(b-a+1-nc-nd+ncd)

Submission status: Accepted

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

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

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

t1 = b // c
t2 = (a - 1) // c
u1 = b // d
u2 = (a - 1) // d
v1 = b // x
v2 = (a - 1) // x

ans = (b - a + 1) - (t1 - t2) - (u1 - u2) + (v1 - v2)
print(ans)

Submission status: Accepted

Solution code:


def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=0 :
        x, y = max(x,y), min(x,y)
        x %= y
    return y
#print(gcd(4,8))

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

cd = int(c*d/gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

Submission status: Accepted

Solution code:
def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    def f(n, c, d):
        return n // c + n // d - n // (c * d // gcd(c, d))
    a, b, c, d = map(int, input().split())
    # print(b - a + 1)
    # print(f(b, c, d))
    # print(f(a - 1, c, d))
    print(b - a + 1 -  f(b, c, d) + f(a - 1, c, d))
    return 0

main()

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())
lcm=(c*d)//gcd(c,d)
num1=(b-a+1)
num2=b//c-(a-1)//c
num3=b//d-(a-1)//d
num4=b//lcm-(a-1)//lcm
ans=num1-num2-num3+num4
print(ans)

Submission status: Accepted

Solution code:
import collections as c
from fractions import gcd
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
A,B,C,D = ip()
cd = C*D//gcd(C,D)
# print(cd)
ans = B-A+1 - ( B//C - (A+C-1)//C + B//D - (A+D-1)//D - B//cd + (A+cd-1)//cd + 1)
# print(B//C - (A+C-1)//C + 1)
# print(B//D - (A+D-1)//D + 1)
# print(B//cd - (A+cd-1)//cd + 1)
print(ans)

Submission status: Accepted

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

# a > b
def m(a, b):
    if a < b:
        a, b = b, a

    if a % b == 0:
        return b
    return m(b, a % b)

def g(a, b):
    return a * b // m(a, b)

num_c = B // C - (A - 1) // C
num_d = B // D - (A - 1) // D
cd = g(D, C)
num_cd = B // cd - (A - 1) // cd

print(B - A + 1 - (num_c + num_d - num_cd))

Submission status: Accepted

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

def n_div(N, a, b):
    return N - (N//a + N//b - N//(a*b//gcd(a,b)))

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

ans = n_div(B, C, D)-n_div(A-1, C, D)

print(ans)

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 count(v, x, y):
  v_x = v // x
  v_y = v // y
  v_xy = v // lcm(x, y)

  return v_x + v_y - v_xy


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

  print(b - a + 1 - (count(b, c, d) - count(a - 1, c, d)))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:

def gcd(x,y):
    if x % y == 0:
        return y
    else:
        return  gcd(y, x%y)
A,B,C,D = list(map(int,input().split()))
LCD = C * D // gcd(C,D)

Bc = B // C
Bd = B // D
Blcd = B // LCD
Bans = B - Bc - Bd + Blcd 

A = A - 1
Ac = A // C
Ad = A // D
Alcd = A // LCD
Aans = A - Ac - Ad + Alcd

print(Bans - Aans)

Submission status: Accepted

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

# n以下でmで割り切れるものの数を求める
def a(n,m):
    return n//m

A,B,C,D = map(int,input().split())
E = C*D//gcd(C,D)
b = A-1 - (a(A-1,C)+a(A-1,D)-a(A-1,E))
c = B - (a(B,C)+a(B,D)-a(B,E))
print(c-b)

Submission status: Accepted

Solution code:
import fractions

f = lambda n, m : n / m
lcm = lambda a, b : a * b / fractions.gcd(a, b)

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

a -= 1
a1 = f(a, c) + f(a, d) - f(a, l)
a2 = f(b, c) + f(b, d) - f(b, l)

print (b - a) - (a2 - a1)

Submission status: Accepted

Solution code:
try:
    from math import gcd
except:
    from fractions import gcd

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

M = C * D // gcd(C, D)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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


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


def func(n, c, d):
    cdlcm = lcm(c,d)
    return n//c + n//d - n//cdlcm

a,b,c,d = li()

print((b-a+1) - (func(b,c,d) - func(a-1,c,d)))

Submission status: Accepted

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