Problem:


Score : 300 points

Problem Statement

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

Constraints

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

1\leq C,D\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

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

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

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

cc=b//c-(a-1)//c
dd=b//d-(a-1)//d

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

dup=b//f-(a-1)//f

ans=b-(a-1)-(cc+dd-dup)

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

def solve(a, b, c, d):
    cd = c * d // fractions.gcd(c, d)

    x = num_factors(c, a, b)
    y = num_factors(d, a, b)
    z = num_factors(cd, a, b)

    return b - a + 1 - x - y + z

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

main()

Submission status: Accepted

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

# 最大公約数
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return y


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

cb = b//c
ca = (a-1)//c
cc = cb-ca

# print(cb, ca, cc)

db = b//d
da = (a-1)//d
dd = db-da

# print(db, da, dd)

cd = c*d // gcd(c, d)
cdb = b//cd
cda = (a-1)//cd
cdcd = cdb-cda

# print(cdb, cda, cdcd)

print(b-a+1-(cc+dd-cdcd))

Submission status: Accepted

Solution code:
import math
import sys
from decimal import *

fin = sys.stdin.readline
A, B, C, D = [Decimal(elem) for elem in fin().split()]


# A以上B以下のCの倍数の個数
def warikiru(A, B, C):
    return (B // C) - math.ceil(A / C) + 1


# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


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


warikiru_num = warikiru(A, B, C) + warikiru(A, B, D) - warikiru(A, B, lcm(C, D))

print(int(B - A + 1 - warikiru_num))

Submission status: Accepted

Solution code:
a, b, c, d = (int(i) for i in 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 divisorNum(cd):
  global a, b
  res = a%cd
  length = b-a+1
  if res!=0:
    first = cd - res
    return (length - (first+1))//cd +1
  else:
    return (length - 1)//cd +1
  
e = lcm(c, d)
ans  = (b-a+1) - divisorNum(c) - divisorNum(d) + divisorNum(e)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
cnt = b - a + 1
li = []

# 1..A..B % C == 0
li.append(b//c)
cnt -= (b // c)
# 1..A % C == 0
li.append((a-1) // c)
cnt += ((a-1) // c)

# 1..A..B % D == 0
li.append(b//d)
cnt -= (b // d)
# 1..A % D == 0
li.append((a-1) // d)
cnt += ((a-1) // d)

# 1..A..B % (CD) == 0
div = (c * d) // gcd(c, d)
li.append(b // div)
cnt += (b // div)
# 1..A % (CD) == 0
li.append((a-1) // div)
cnt -= ((a-1) // div)

print(cnt)

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

Submission status: Accepted

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

A -= 1

Cnum = B // C - A // C
Dnum = B // D - A // D

Cnum = B - A - Cnum
Dnum = B - A - Dnum

if(C < D):
    C, D = C, D

x = C*D

r = C % D

while(r != 0):
    C = D
    D = r
    r = C % D

LCM_CD = x // D

CDnum = B // LCM_CD - A // LCM_CD

CDnum = B - A - CDnum

ans = Cnum + Dnum - CDnum

print(ans)

Submission status: Accepted

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


def acinput():
    return list(map(int, input().split(" ")))
def lcm(x, y):
    return x*y //gcd(x, y)

a, b, c, d = acinput()
l = lcm(c, d)
CD = b//l-(a-1)//l
nC = b//c-(a-1)//c
nD = b//d-(a-1)//d

res = b-a+1-(nC+nD-CD)
print(int(res))

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# A以上B以下にXの倍数が幾つあるか？ 1 <= A <= B
def check(A, B, X):
    x = (A-1) // X
    y = (B-0) // X
    return y - x

import fractions

def main():
    A, B, C, D = i2nn()
    # A以上B以下の数
    n = B - A + 1
    # Cの倍数
    n -= check(A, B, C)
    # Dの倍数
    n -= check(A, B, D)
    # GCD(C, D)の倍数
    E = C * D // fractions.gcd(C, D)
    n += check(A, B, E)
    n = int(n)
    print(n)

main()

Submission status: Accepted

Solution code:
# ABC131C - Anti-Division
from fractions import gcd


def main():
    a, b, c, d = list(map(int, input().rstrip().split()))
    total = b - a + 1
    a -= 1
    divisible = 0
    div_c = b // c - a // c
    divisible += div_c
    div_d = b // d - a // d
    divisible += div_d
    lcm = c * d // gcd(c, d)
    div_lcm = b // lcm - a // lcm
    divisible -= div_lcm
    print(total - divisible)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

l = lcm(C, D)

A = A-1
x = (B-A)
y = (B//C - A//C)
z = (B//D - A//D)
a = (B//l - A//l)
print(x+a - (y+z))

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

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        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())
a = B//C-(A-1)//C
b = B//D-(A-1)//D
c  =lcm(C,D)
d = B//c-(A-1)//c
e = B - A +1 - a -b + d 
print(e)

Submission status: Accepted

Solution code:
import fractions

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


c_div1 = int((a-1) // c)
c_div2 = int(b // c)
d_div1 = int((a-1) // d) 
d_div2 = int(b // d)
lcm_div1 = int((a-1) // lcm)
lcm_div2 = int(b // lcm)

ans = int(c_div2 - c_div1) + int(d_div2 - d_div1) - int(lcm_div2 - lcm_div1)
#print(c_div1,c_div2,d_div1,d_div2,lcm_div1,lcm_div2)
print(int(b - a - ans + 1))

Submission status: Accepted

Solution code:
def lcm(x, y):
    import fractions
    return (x * y) // fractions.gcd(x, y)
a,b,c,d = map(int, input().split())
import math
res = b - a + 1
#print(res)
res -= b // c - (a-1) // c
#print("!" + str(math.ceil(b / c) - math.ceil(a / c)))
#print(res)
res -= b // d - (a-1) // d
#print("!" + str(math.ceil(b / d) - math.ceil(a // d)))
#print(res)
res += b // lcm(c, d) - (a-1) // lcm(c,d)
#print("!" + str(math.ceil(b / lcm(c, d)) - math.ceil(a / lcm(c,d))))
print(res)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x,y):
    return (x*y) // gcd(x,y)
A,B,C,D =  list(map(int,input().split(" ")))
CD = lcm(C,D)
 
divisibleC = B // C - (A-1)//C
divisibleD = B // D - (A-1) // D
divisibleCD = B//CD - (A-1)//CD 
divisible = divisibleC +divisibleD - divisibleCD
numbers = B-A + 1
print(numbers -divisible )

Submission status: Accepted

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

e=b//c
f=-(-a//c)

ans=e-f+1

g=b//d
h=-(-a//d)

ans=ans+g-h+1

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

j=b//i
k=-(-a//i)

ans=ans-(j-k+1)

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

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

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)

cd=lcm(c,d)

nac=a//c
nbc=b//c
nad=a//d
nbd=b//d
nacd=a//(cd)
nbcd=b//(cd)


nc=nbc-nac
if a%c==0: nc+=1
#print(nc)
nd=nbd-nad
if a%d==0: nd+=1
#print(nd)
ncd=nbcd-nacd
if a%(cd)==0: ncd+=1
#print(ncd)

ans=b-a+1-(nc+nd-ncd)

print(ans)

Submission status: Accepted

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

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

a, b, c, d = list(map(int, input().split()))
ttt = lcm(c, d)
tt = b-a+1
ta = b//c - (a-1)//c
tb = b//d - (a-1)//d
tc = b//ttt - (a-1)//ttt
print(tt-ta-tb+tc)

Submission status: Accepted

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

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

cmax=b//c
cmin=(a-1)//c
dmax=b//d
dmin=(a-1)//d
cd=c*d//gcd(c, d)
cdmax=b//cd
cdmin=(a-1)//cd

yakuc=cmax-cmin
yakud=dmax-dmin
yakucd=cdmax-cdmin

yaku=yakuc+yakud-yakucd
ans=b-a+1-yaku
print(ans)

Submission status: Accepted

Solution code:
import fractions

A, B, C, D = map(int, input().split())
E = (C * D) // fractions.gcd(C, D)
num_c = B // C - A // C + (1 if A % C == 0 else 0)
num_d = B // D - A // D + (1 if A % D == 0 else 0)
num_e = B // E - A // E + (1 if A % E == 0 else 0)
num = B - A + 1 - (num_c + num_d - num_e)
print(num)

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)

cc=(b//c)-((a-1)//c)
dd=(b//d)-((a-1)//d)
cd=(b//e)-((a-1)//e)
print((b-a+1)-(cc+dd-cd))

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

lcm_c_d = lcm(C, D)

N = B - A + 1

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


ans = N - count_C - count_D + count_CD

print(ans)

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().rstrip().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+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

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

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

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

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

b_num = B - (B // C + B // D - B // (C*D))
a_num = A - (A // C + A // D - A // (C*D))

b_num2 = B // z - B // (C*D)
a_num2 = A // z - A // (C*D)



print(b_num - a_num + (b_num2 - a_num2))

Submission status: Accepted

Solution code:
import os, sys, re, math

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

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

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

ret = B // C - (A-1) // C
ret += B // D - (A-1) // D
ret -= B // lcm - (A-1) // lcm
print(B-A+1-ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd



a, b, c, d = map(int, input().split())
cd_gcd = gcd(c, d)
cd_lcm = c*d // cd_gcd
b_div_d = b // d
a_div_d = a // d
if a % d == 0:
    b_div_d += 1
b_div_c = b // c
a_div_c = a // c
if a % c == 0:
    b_div_c += 1
b_div_c_d = b // cd_lcm
a_div_c_d = a // cd_lcm
if a % cd_lcm == 0:
    b_div_c_d += 1
hoshugo_num = b_div_d - a_div_d + b_div_c - a_div_c - (b_div_c_d - a_div_c_d)
print(int(b - a + 1 - hoshugo_num))

Submission status: Accepted

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

def lcm(x, y):
    return (x * y) // fra.gcd(x, y)
  
def wari(max, k):
  return (max // k)

lcmCD = lcm(C, D)
bot = A - (wari(A, C) + wari(A, D) - wari(A, lcmCD))
top = B - (wari(B, C) + wari(B, D) - wari(B, lcmCD))

if A % C != 0:
  if A % D != 0:
    bot -= 1
  
print(top - bot)

Submission status: Accepted

Solution code:
a, b, c, d = (int(_) for _ in input().split())
def gcd(x, y):
   while y:
       x, y = y, x % y
   return x

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

div = lcm(c,d)

if a % c == 0:
    start = a //c
else:
    start = a // c + 1
stop = b // c 
diff = b - a + 1
diff -= (stop - start + 1)

if a % d == 0:
    start = a // d
else:
    start = a // d + 1
stop = b // d
diff -= (stop - start + 1)

if a % div == 0:
    start = a//div
else:
    start = a // div + 1
stop = b // div
diff += (stop - start + 1)

print(diff)

Submission status: Accepted

Solution code:
import fractions
s=input().split()
a,b,c,d=int(s[0]),int(s[1]),int(s[2]),int(s[3])
g=fractions.gcd(c,d)
l=(d*c)//g
e=-((a-1)//c)+b//c-((a-1)//d)+b//d+(a-1)//l-(b//l)
print(b-a+1-e)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
c_val = (b // c) - ((a - 1) // c)
d_val = (b // d) - ((a - 1) // d)
cd_gcd = fractions.gcd(c, d)
cd_lcm = c * d // cd_gcd
cd_lcm_val = (b // cd_lcm) - ((a - 1) // cd_lcm)
cd_val = c_val + d_val - cd_lcm_val
print((b - a + 1) - cd_val)

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split(' '))
res1 = a // c
res2 = a // d
res3 = b // c
res4 = b // d
tmp1 = c
tmp2 = d
if tmp1 < tmp2:
    while tmp1:
        tmp = tmp1
        tmp1 = tmp2 % tmp1
        tmp2 = tmp
    result = tmp2
else:
    if tmp1 >= tmp2:
        while tmp2:
            tmp = tmp2
            tmp2 = tmp1 % tmp2
            tmp1 = tmp
        result = tmp1
result = c * d // result
res5 = a // result
res6 = b // result
i = res3 - res1
j = res4 - res2
k = res6 - res5
if a % c == 0:
    i += 1
if a % d == 0:
    j += 1
if a % result == 0:
    k += 1

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

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
def count(A, B, div):
    if B % div >= A % div and A % div > 0:
        return (B - A) // div
    else:
        return (B - A) // div + 1

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

rev = count(A, B, C) + count(A, B, D) - count(A, B, C*D//gcd(C, D))
print(B - A + 1 - rev)

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

def count_num(num):
  a_1 = num//c
  a_2 = num//d
  a_3 = num//(c * d // gcd(c, d))
  return num - (a_1 + a_2 - a_3)

print(int(count_num(b) - count_num(a-1)))

Submission status: Accepted

Solution code:
def main():
     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())
     ans=b-a+1
     ans-=(b)//c-(a-1)//c
     ans-=(b)//d-(a-1)//d
     cd=lcm(c,d)
     ans+=(b)//(cd)-(a-1)//(cd)
     print(ans)
     
if __name__=='__main__':
     main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = map(int, input().split())
lcm = c // fractions.gcd(c,d)*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 = (int(i) for i in input().split())
def lcm(x, y):
    return (x * y) // gcd(x, y)

all = b-a+1
c_cnt = b//c-(a-1)//c
d_cnt = b//d-(a-1)//d
lcm_cnt = b//lcm(c,d)-(a-1)//lcm(c,d)
#print(c_cnt,d_cnt,lcm_cnt)
print(all-(c_cnt+d_cnt)+lcm_cnt)

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

round=lambda x:(x*2+1)//2

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

Submission status: Accepted

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

n = b - a + 1
x0 = (a - 1)// c
y0 = b // c
x1 = (a - 1) // d
y1 = b // d
x2 = (a - 1) // (c * d // gcd(c, d))
y2 = b // (c * d // gcd(c, d))

print(n - ((y0 - x0) + (y1 - x1) - (y2 - x2)))

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

AdivisibleC = (A - 1) // C
AdivisibleD = (A - 1) // D
AdivisibleCD = (A - 1) // lcm(C, D)
AindivisibleCD = (A - 1) - (AdivisibleC + AdivisibleD - AdivisibleCD)

BdivisibleC = B // C
BdivisibleD = B // D
BdivisibleCD = B // lcm(C, D)
BindivisibleCD = B - (BdivisibleC + BdivisibleD - BdivisibleCD)

print(BindivisibleCD - AindivisibleCD)

Submission status: Accepted

Solution code:

import fractions

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

ans = b - a + 1 

if d%c == 0:#4 8 4 2
    ans -= b//c - a//c + (0 if a%c != 0 else 1)

else:
    x = b // c - a//c + (0 if a%c != 0 else 1)
    y = b // d - a//d + (0 if a%d != 0 else 1)

    lcm = c*d // fractions.gcd(c,d)
    t = b //lcm - a//lcm + (1 if a >= lcm and a%lcm ==0 else 0)

    ans = ans -x-y+t
#    print(x,y,t,lcm,ans)

#    ans += t 


print(ans)

Submission status: Accepted

Solution code:
import fractions

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



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

lcm_cd = lcm_base(c, d)

print((b-a+1)-(b//c + b//d - b//lcm_cd) + ((a-1)//c + (a-1)//d - (a-1)//lcm_cd))

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

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

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

def main():
    A, B, C, D = [int(c) for c in input().split()]
    N_U = (B) - (A - 1)
    N_C = B // C - (A - 1) // C
    N_D = B // D - (A - 1) // D
    N_C_D = int(B // lcm(C, D) - (A - 1) // lcm(C, D))
    excluded_N_C_D = N_C + N_D - N_C_D
    print(int(N_U - excluded_N_C_D))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def f(a,b,c):
    return (b - a + 1) // c + (1 if b % c <= a % c else 0)

if c != 1 and d != 1:
    print ((b-a+1) - (b // c - ceil(a / c) + 1) - (b // d - ceil(a / d) + 1) + (b // lcm(c, d) - ceil(a / lcm(c, d)) + 1))
else:
    print (0)

Submission status: Accepted

Solution code:
import fractions


class AntiDivision:
    def __init__(self):
        self.A, self.B, self.C, self.D = map(int, input().split())

    def cal(self):
        a_b_count = self.B - self.A + 1
        lcm = (self.C * self.D) // fractions.gcd(self.C, self.D)
        c_count = self.B // self.C - (self.A - 1) // self.C
        d_count = self.B // self.D - (self.A - 1) // self.D
        lcm_count = self.B // lcm - (self.A - 1) // lcm

        print(a_b_count - c_count - d_count + lcm_count)


antiDivision = AntiDivision()
antiDivision.cal()

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 = map(int, input().strip().split())

a_c = A // C
a_c_mod = A % C
b_c = B // C
a_d = A // D
a_d_mod = A % D
b_d = B // D

l = lcm(C, D)

a_cd = A // l
a_cd_mod = A % l
b_cd = B // l

if a_c_mod == 0:
    a_c -= 1

if a_d_mod == 0:
    a_d -= 1

if a_cd_mod == 0:
    a_cd -= 1

print((B - A + 1) - (b_c - a_c) - (b_d - a_d) + (b_cd - a_cd))

Submission status: Accepted

Solution code:
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

lcm_cd = lcm(C,D)

tmp_all_c=B//C
tmp_all_d=B//D
tmp_all_cd=B//lcm_cd
tmp_all=tmp_all_c+tmp_all_d-tmp_all_cd

tmp_untilA_c=(A-1)//C
tmp_untilA_d=(A-1)//D
tmp_untilA_cd=(A-1)//lcm_cd
tmp_untilA=tmp_untilA_c+tmp_untilA_d-tmp_untilA_cd

print((B-A+1)-(tmp_all-tmp_untilA))

Submission status: Accepted

Solution code:
from sys import stdin

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

def count_div(a, b, div):
    ac = a // div
    if ac * div < a:
        ac += 1
    bc = b // div
    if bc * div > b:
        bc -= 1
    return bc - ac + 1

if __name__ == '__main__':
    A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]

    nc = count_div(A, B, C)
    
    nd = count_div(A, B, D)
    
    CD = int(C * D / gcd(C, D))
    ncd = count_div(A, B, CD)
    
    n = B - A + 1
    
    ans = n - (nc + nd - ncd)
    print(ans)

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

if c > d:
	tmp = c
	c = d
	d = tmp
lcm = (c * d) // gcd(c, d)

Cstart = a - (a % c) + c if a % c != 0 else a
Cend = b - (b % c)
Dstart = a - (a % d) + d if a % d != 0 else a
Dend = b - (b % d)
LCMstart = a - (a % lcm) + lcm if a % lcm != 0 else a
LCMend = b - (b % lcm)

# print(Cstart, Cend)
# print(Dstart, Dend)
# print(LCMstart, LCMend)
# print()

Ccnt, Dcnt, LCMcnt = 0, 0, 0
if Cstart <= Cend:
	Ccnt = (Cend - Cstart) // c + 1
if Dstart <= Dend:
	Dcnt = (Dend - Dstart) // d + 1
if LCMstart <= LCMend:
	LCMcnt = (LCMend - LCMstart) // lcm + 1

# print(Ccnt, Dcnt, LCMcnt)
# print((Cend - Cstart)//4, Ccnt)

print((b-a+1) - Ccnt - Dcnt + LCMcnt)

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())
if A%C == 0:
    wid = A
else:
    wid = (A//C + 1) * C
if wid > B:
    c_num = 0
else:
    c_num = (B-wid) // C + 1

if A%D == 0:
    wid = A
else:
    wid = (A//D + 1) * D
if wid > B:
    d_num = 0
else:
    d_num = (B-wid) // D + 1

E = lcm(C, D)
if A%E == 0:
    wid = A
else:
    wid = (A//E + 1) * E
if wid > B:
    e_num = 0
else:
    e_num = (B-wid) // E + 1

print(B - A - (c_num + d_num - e_num) + 1)

Submission status: Accepted

Solution code:
import fractions 

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

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

print(B - A + 1 - (B // C - (A - 1) // C) - (B // D - (A - 1) // D) + (B // gcd - (A - 1) // gcd))

Submission status: Accepted

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

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

def lcm(x, y):
    return int(x/gcd(x, y)*y)
  
E = lcm(C,D)

C_min = int(A-1) // C
C_max = B // C
D_min = int(A-1) // D
D_max = B // D
E_min = int(A-1) // E
E_max = B // E
min_num = C_min + D_min - E_min
max_num = C_max + D_max - E_max
ans = B - (A-1) - (max_num - min_num)
print(ans)

Submission status: Accepted

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

saishou=(c*d)//fractions.gcd(c, d)#最小公倍数
warikiri_a=[]
warikiri_b=[]
amari_a=[]
amari_b=[]
warikiri_a.append(a//c)
warikiri_a.append(a//d)
warikiri_a.append(a//saishou)
warikiri_b.append(b//c)
warikiri_b.append(b//d)
warikiri_b.append(b//saishou)
amari_a.append(a%c)
amari_a.append(a%d)
amari_a.append(a%saishou)
amari_b.append(b%c)
amari_b.append(b%d)
amari_b.append(b%saishou)
list=[]
for i in range(3):
    if amari_a[i]==0:
        list.append(warikiri_b[i]-warikiri_a[i]+1)
    else:
        list.append(warikiri_b[i]-warikiri_a[i])

for i in range(3):
    if list[i]<0:
        list[i]=0
print((b-a+1)-(list[0]+list[1]-list[2]))

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
    A, B, C, D = map(int, input().split())
    Q_AC, R_AC = A // C, A % C
    Q_AD, R_AD = A // D, A % D
    Q_BC, R_BC = B // C, B % C
    Q_BD, R_BD = B // D, B % D
    Q_ACD, R_ACD = A // lcm(C, D), A % lcm(C, D)
    Q_BCD, R_BCD = B // lcm(C, D), B % lcm(C, D)
    N_C = num_baisu(Q_AC, Q_BC, R_AC, R_BC)
    N_D = num_baisu(Q_AD, Q_BD, R_AD, R_BD)
    N_CD = num_baisu(Q_ACD, Q_BCD, R_ACD, R_BCD)
    print(B - A + 1 - (N_C + N_D - N_CD))
    return


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


def num_baisu(Q_A, Q_B, R_A, R_B):
    if R_A == 0 and R_B == 0:
        return Q_B - Q_A + 1
    elif R_A == 0 and R_B != 0:
        return Q_B - Q_A + 1
    elif R_A != 0 and R_B == 0:
        return Q_B - (Q_A + 1) + 1
    else:
        return Q_B - (Q_A + 1) + 1


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

g = gcd(C, D)

print((B - A + 1) - (B // C - (A - 1) // C) - (B // D - (A - 1) // D) + (B // (C * D // g) - (A - 1) // (C * D // g)))

Submission status: Accepted

Solution code:
# coding: utf-8
import fractions

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


a, b, c, d = map(int, input().split())
ac = (a - 1) // c
ad = (a - 1) // d
acd = (a - 1) // lcm(c, d)
bc = b // c
bd = b // d
bcd = b // lcm(c, d)
print((b - a + 1) - ((bc + bd - bcd) - (ac + ad - acd)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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


def main():
    A, B, C, D = [int(i) for i in input().split()]
    # X : AとBの間の整数の数
    X = B - A + 1
    # Y : AとBの間でCの倍数の数
    Y = (B // C) - ((A - 1) // C)
    # Z : AとBの間でDの倍数の数
    Z = (B // D) - ((A - 1) // D)
    # V : CとDの最小公倍数
    V = (C * D) // gcd(C, D)
    # W : AとBの間でVの倍数の数
    W = (B // V) - ((A - 1) // V)
    print(X - Y - Z + W)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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


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

CD = lcm(C, D)
count = B - A
count -= (B // C) - ((A - 1) // C + 1)
count -= (B // D) - ((A - 1) // D + 1)
count += (B // CD) - ((A - 1) // CD + 1)

print(count)

Submission status: Accepted

Solution code:
A, B, C, D = [int(e) for e in input().split()]
E = max(C, D)
F = min(C, D)

mod = 1
while mod > 0:
  mod = E % F
  if mod == 0:
    break
  else:
    E = F
    F = mod
G = C*D // F

A_B = []
for AB in [A-1, B]:
  AB_c = AB // C
  AB_d = AB // D
  AB_g = AB // G
  A_B.append(AB_c + AB_d - AB_g)
can_divide = A_B[1] - A_B[0]
ans = (B - (A-1)) - can_divide
print(ans)

Submission status: Accepted

Solution code:

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

#N = int(input())

#list(map(int,input().split()))

cnt = B-A+1

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


A_C = A//C
A_dC = A%C

B_C = B//C
#B_dC = B%C

A_D = A//D
A_dD = A%D

B_D = B//D
#B_dD = B%D

A_E = A//E
A_dE = A%E

B_E = B//E
#B_dE = B%E

C_cnt = B_C - A_C
if A_dC == 0:
    C_cnt += 1
D_cnt = B_D - A_D
if A_dD == 0:
    D_cnt += 1
E_cnt = B_E - A_E
if A_dE == 0:
    E_cnt += 1  

ans = cnt - C_cnt - D_cnt + E_cnt
print(int(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)

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

if div <= b:
    x_div = a//div
    y_div = b//div
    if a%div == 0:
        x_div -= 1
else:
    x_div = 0
    y_div = 0
x_c = a//c
if a%c == 0:
    x_c -=1
y_c = b//c
x_d = a//d
if a%d == 0:
    x_d -= 1
y_d = b//d
print(b-a+1+(y_div-x_div)-(y_c-x_c)-(y_d-x_d))

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

ac = (A-1) // C
bc = B // C
ad = (A-1) // D
bd = B // D
alcm = (A-1) // lcm
blcm = (B) // lcm

num_c = bc - ac
num_d = bd - ad
num_lcm = blcm - alcm

ans = (B - A + 1) - (num_c + num_d - num_lcm)

print(ans)

Submission status: Accepted

Solution code:
# C問題
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A, B, C, D = map(int, input().split())
E = lcm(C, D)
ac = A // C
bc = B // C
ad = A // D
bd = B // D
ae = A // E
be = B // E
if A % C == 0:
    ac -= 1
if A % D == 0:
    ad -= 1
if A % E == 0:
    ae -= 1
xx = bc - ac + bd - ad
yy = be - ae
print(B - A + 1 - xx + yy)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

bb = int((b // c) + (b // d) - (b // lcm))

aa = int(((a-1) // c) + ((a-1) // d) - ((a-1) // lcm))

print((b-a) - int(bb-aa) + 1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left
from math import floor, ceil


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

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

    def floor(self, a, b):
        return (a + (b - 1)) // b

    def main(self):
        A, B, C, D = map(int, input().split())
        v = self.lcm(C, D)
        c_and_d = B//v - self.floor(A, v) + 1
        only_c = B//C - self.floor(A, C) + 1
        only_d = B//D - self.floor(A, D) + 1
        res = (B - A + 1) - (only_c + only_d - c_and_d)
        print(res)

if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

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

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

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

ca = (A-1) // C
cb = B // C
c = cb - ca

da = (A-1) // D
db = B // D
d = db - da

lcm_cd = lcm(min(C,D), max(C,D))
cda = (A-1) // lcm_cd
cdb = B // lcm_cd
cd = cdb - cda

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