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 statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
a,b,c,d = readInts()
ad = a-1
cdg = gcd(c,d)
cdl = c*d//cdg
b = b - b//c - b//d + b//cdl
ad = ad - ad//c - ad//d + ad//cdl
print(b-ad)

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
lcm = (C * D) // math.gcd(C, D)
waruC = B//C-(A-1)//C
waruD = B//D-(A-1)//D
waruCD = B//lcm-(A-1)//lcm
ans = B-A+1-(waruC+waruD-waruCD)
print(ans)

Submission status: Accepted

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

a = a - 1


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


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

a_c = a // c
b_c = b // c
a_d = a // d
b_d = b // d
a_cd = a // cd
b_cd = b // cd

res = b - (b_c + b_d - b_cd) - (a - (a_c + a_d - a_cd))
print(res)

Submission status: Accepted

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

#import fractions
import math
from functools import reduce
def lcm_base(x, y):
  #return (x * y) // fractions.gcd(x, y)
  return (x * y) // math.gcd(x, y)

l = lcm_base(c, d)

r = b//l-(a-1)//l

#print(s, t, r)

ans = b-a+1-(s+t-r)
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
def calc(a,b,n):
  return b//n-(a-1)//n
def solve():
  A, B, C, D = map(int, input().split())
  ans = B-A+1-calc(A,B,C)-calc(A,B,D)+calc(A,B,C*D//gcd(C,D))
  return ans
print(solve())

Submission status: Accepted

Solution code:
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
A,B,C,D = map(int,input().split())
c1 = B//C-(A-1)//C
d1 = B//D-(A-1)//D
E = (C//gcd(C,D))*D
e1 = B//E-(A-1)//E
print(B-A+1-c1-d1+e1)

Submission status: Accepted

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

C = b//c - (a-1)//c
D = b//d - (a-1)//d
x = c*d//math.gcd(c,d)
CD = b//x - (a-1)//x

print((b-a+1) - (C+D-CD))

Submission status: Accepted

Solution code:
from math import gcd

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

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

a_cnt = 0
a_cnt = (b//c) - ((a-1)//c)
b_cnt = (b//d) - ((a-1)//d)

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

ans = (b-a+1) - a_cnt -b_cnt + ab_cnt
print(ans)

Submission status: Accepted

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

from math import gcd
def cnt(n):
    lcm = c//gcd(c,d)*d
    return n - n//c - n//d + n//lcm
print(cnt(b)-cnt(a-1))

Submission status: Accepted

Solution code:
import math
def lcm(x,y):
    return (x*y)//math.gcd(x,y)
a,b,c,d=map(int,input().split())
bc=b//c
bd=b//d
bcd=b//lcm(c,d)
x=b-(bc+bd-bcd)
a=a-1
ac=a//c
ad=a//d
acd=a//lcm(c,d)
y=a-(ac+ad-acd)
print(x-y)

Submission status: Accepted

Solution code:
A,B,C,D=map(int,input().split())
def f(x):
  return B//x-(A-1)//x
import math
E=int(C*D/math.gcd(C,D))
print(B-A+1-f(C)-f(D)+f(E))

Submission status: Accepted

Solution code:
import math
A,B,C,D=map(int,input().split())
def X(x):
    c=x//C
    d=x//D
    l=C*D//math.gcd(C,D)
    return x-c-d+(x//l)
print(X(B)-X(A-1))

Submission status: Accepted

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

a_div_c = (a-1) // c
a_div_d = (a-1) // d
a_div_cd = (a-1) // (c * d // math.gcd(c, d))
b_div_c = b // c
b_div_d = b // d
b_div_cd = b // (c * d // math.gcd(c, d))

y = b - (b_div_c + b_div_d - b_div_cd)
x = (a - 1) - (a_div_c + a_div_d - a_div_cd)

print(y-x)

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int,input().split())
lcm_cd=c*d//math.gcd(c,d)
c_cnt=b//c-(a-1)//c
d_cnt=b//d-(a-1)//d
cd_cnt=b//lcm_cd-(a-1)//lcm_cd
print(b-a+1-c_cnt-d_cnt+cd_cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

a, b, c, d = map(int, input().split())
cd = (c * d) // math.gcd(c, d)
u = b//c + b//d - b//cd
l = (a-1)//c + (a-1)//d - (a-1)//cd

print(b - a + 1 - u + l)

Submission status: Accepted

Solution code:
import math

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

u = b//c + b//d - b//l
l = (a-1)//c + (a-1)//d - (a-1)//l

print(b - a + 1 - u + l)

Submission status: Accepted

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

divc = b//c-(a-1)//c
divd = b//d-(a-1)//d
import math
l = c*d//math.gcd(c,d)
divl = b//l-(a-1)//l
print(b-a+1-divc-divd+divl)

Submission status: Accepted

Solution code:
from math import gcd
lcm = lambda x,y: (x*y)//gcd(x,y)
A,B,C,D = [int(i) for i in input().split()]
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 math
def lcm(x, y):return (x * y) // math.gcd(x, y)
a,b,c,d=map(int,input().split())

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

Submission status: Accepted

Solution code:
import math

a, b, c, d = map(int, input().split())
total = b - a + 1
c_cnt = b // c - (a-1) // c
d_cnt = b // d - (a-1) // d
common_div = (c * d) // math.gcd(c, d)
common_cnt = b // common_div - (a-1) // common_div
total = total - c_cnt - d_cnt + common_cnt
print(total)

Submission status: Accepted

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

def cnt(x):
    return B//x - A//x + (A%x==0)

from math import gcd

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

print((B-A+1)-cnt(C)-cnt(D)+cnt(l))

Submission status: Accepted

Solution code:
def binary_search_int(ok, ng, test, p):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid, p):
            ok = mid
        else:
            ng = mid
    return ok

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

from math import gcd

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

def test1(x, p):
    return x*p<=B
b = [binary_search_int(0,10**18+1,test1, x) for x in [C, D, l]]

def test2(x, p):
    return x*p>=A

a = [binary_search_int(10**18+1, 0,test2, x) for x in [C, D, l]]

res = [x-y+1 if (x!=0 and y!=10**18+1) else 0 for x, y in zip(b, a)]


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

Submission status: Accepted

Solution code:
import math
from decimal import Decimal
a, b, c, d = list(map(int, input().split()))

cnt = 0
numc = b//c - math.ceil(Decimal(a)/Decimal(c)) + 1
numd = b//d - math.ceil(Decimal(a)/Decimal(d)) + 1

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

cd = (c*d) // gcd(c, d)
numcd = b//cd - math.ceil(Decimal(a)/Decimal(cd)) + 1

cnt = b - a + 1 - numc - numd + numcd

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

A=a-1
l=c*d//math.gcd(c,d)
acou=(A//c)+(A//d)-int((A//l))
bcou=(b//c)+(b//d)-int((b//l))

print(count-(bcou-acou))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

a,b,c,d=map(int,open(0).read().split())

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

nc=b//c-(a-1)//c
nd=b//d-(a-1)//d
ne=b//e-(a-1)//e

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc131_c

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

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

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

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

Submission status: Accepted

Solution code:
from math import gcd


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


a, b, c, d = map(int, input().split())
e = lcm(c, d)
num_e = b // e - (a - 1) // e
num_c = b // c - (a - 1) // c
num_d = b // d - (a - 1) // d
num_can_div = num_c + num_d - num_e

print((b - a) - num_can_div + 1)

Submission status: Accepted

Solution code:
import math

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int,input().split())
mc = b//c-(a-1)//c
md = b//d-(a-1)//d
cd = (c*d)//math.gcd(c,d)
mcd = b//cd - (a-1)//cd

print(b-a+1 - mc-md+mcd)

Submission status: Accepted

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

num1=b//c
num2=b//d
num3=b//g
num4=(a-1)//c
num5=(a-1)//d
num6=(a-1)//g


print(b-a+1-(num1+num2-num3-num4-num5+num6))

Submission status: Accepted

Solution code:
import numpy as np
A,B,C,D = map(int,input().split())
E = np.lcm(C,D)
print(1+B-A-B//C+(A-1)//C-B//D+(A-1)//D+B//E-(A-1)//E)

Submission status: Accepted

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

x = (a - 1) - (a - 1) // c - (a - 1) // d + (a - 1) // lcm
y = b - b // c - b // d + b // lcm

print(y - x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

A, B, C, D = [int(x) for x in input().split(" ")]
lcm_c_d = (C * D) // math.gcd(C, D)
num_c = (B // C) - (A - 1) // C
num_d = (B // D) - (A - 1) // D
num_cd = (B // lcm_c_d) - (A - 1) // lcm_c_d
print(B - A - num_c - num_d + num_cd + 1)

Submission status: Accepted

Solution code:
from math import gcd


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


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


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

Submission status: Accepted

Solution code:
import math

def getDivCount( a, b, x ):
    count=0
    if a!=0 :
        count+=b//x-(a-1)//x
    else:
        count+=b//x+1
    return count

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

count = b-a+1
count -= getDivCount(a,b,c)
count -= getDivCount(a,b,d)
count += getDivCount(a,b,c*d//math.gcd(c,d))
print(count)

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
cdiv = B // C - (A - 1) // C
ddiv = B // D - (A - 1) // D
lcm = (C * D) // math.gcd(C, D)
cddiv = B // lcm - (A - 1) // lcm
ans = (B - A + 1) - (cdiv + ddiv - cddiv)
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 = list(map(int, input().split()))
Bc = B // C
Bd = B // D
Ac = (A - 1) // C
Ad = (A - 1) // D
lcm = C * D // gcd(C, D)
Blcm = B // lcm
Alcm = (A - 1) // lcm
print((B - A + 1) - ((Bc - Ac) + (Bd - Ad) - (Blcm - Alcm)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import gcd
#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())
a -= 1
tmp1 = b - (b//c + b//d - b//(lcm(c, d)))
tmp2 = a - (a//c + a//d - a//(lcm(c, d)))

print(tmp1-tmp2)

Submission status: Accepted

Solution code:
from math import gcd
a, b, c, d = map(int, input().split())
whole = b - a + 1
sum_c = b//c - (a-1)//c
sum_d = b//d - (a-1)//d
div = (c*d)//gcd(c, d)
sum_c_d = b//div - (a-1)//div
print(whole - ((sum_c + sum_d) - sum_c_d))

Submission status: Accepted

Solution code:
from math import gcd 
a, b, c, d = map(int, input().split())
n = b-a+1

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

def cal(x, a, b):
    cnt = b//x - a//x
    if a%x == 0:
        cnt += 1
    return cnt

ans = cal(c, a, b)
ans += cal(d, a, b)
ans -= cal(lcm(c, d), a, b)
print(n - ans)

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
total = B-A+1
A -= 1
waruC = (B//C)-(A//C)
waruD = (B//D)-(A//D)
CD = C * D // math.gcd(C, D)
waruCD = (B//CD)-(A//CD)
print(total-waruC-waruD+waruCD)

Submission status: Accepted

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

E = B//C + (-A//C) + 1
F = B//D + (-A//D) + 1
G = B//lcm(C,D) + (-A//lcm(C,D)) + 1
H = E + F - G
print(B - A + 1 - H)

Submission status: Accepted

Solution code:
import math
l = list(map(int,input().split()))

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

l[0] -= 1
la = l[0] - l[0] // l[2] - l[0] // l[3] + l[0] // lcm(l[2], l[3])
lb = l[1] - l[1] // l[2] - l[1] // l[3] + l[1] // lcm(l[2], l[3])
print(lb - la)

Submission status: Accepted

Solution code:
import numpy as np

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

cdlcm = np.lcm(c,d)

a_c = (a-1) // c
b_c = b // c
a_d = (a-1) // d
b_d = b // d
a_cd = (a-1) // (cdlcm)
b_cd = b // (cdlcm)

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
a, b, c, d = map(int, input().split())
lcm = c*d//gcd(c, d)
cc = b//c - (a//c - (a%c==0))
cd = b//d - (a//d - (a%d==0))
clcm = b//lcm - (a//lcm - (a%lcm==0))
print(b-a+1 - (cc + cd - clcm))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from math import gcd

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

def solve(a,b,c,d):
  def countNonDivisor(n,c,d):
    return n - n//c - n//d + n//lcm(c,d)
  return countNonDivisor(b,c,d) - countNonDivisor(a-1,c,d)



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

  return

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def common_multiple(x, y):
    for i in range(2, min(x, y)+1):
        x0, y0 = x % i, y % i
        if x0 == 0 or y0 == 0:
            return common_multiple(x // i if x0 == 0 else x, y // i if y0 == 0 else y) * i
    return x * y

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

M = common_multiple(C, D)
B0 = B // C + B // D - B // M
A0 = A // C + A // D - A // M
print(B - A - B0 + A0)

Submission status: Accepted

Solution code:
def common_multiple(x, y):
    for i in range(2, min(x, y)+1):
        if x % i == 0 or y % i == 0:
            return common_multiple(x // i if x % i  == 0 else x, y // i if y % i == 0 else y) * i
    return x * y

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

M = common_multiple(C, D)
B0 = B // C + B // D - B // M
A0 = A // C + A // D - A // M
print(B - A - B0 + A0)

Submission status: Accepted

Solution code:
def common_multiple(x, y):
    for i in range(2, min(x, y)+1):
        mod_x = x % i
        mod_y = y % i
        if (mod_x == 0 and mod_y == 0):
            return common_multiple(x // i, y // i) * i
        if (mod_x == 0):
            return common_multiple(x // i, y) * i
        if (mod_y == 0):
            return common_multiple(x, y // i) * i
    return  x * y

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

M = common_multiple(C,D)
B0 = B // C + B // D - B // M
A0 = A // C + A // D - A // M
print(B - A - B0 + A0)

Submission status: Accepted

Solution code:
import math
from typing import List

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

def gcd(c, d):
    mod = 1
    while mod > 0:
        mod = c % d
        c = d
        d = mod
    return c

def f(x: int, c: int, d: int):
    return x - x // c - x // d + x // (c * d // gcd(c, d))

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

Submission status: Accepted

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

def f(a, b, c):
    return b // c - (a + c - 1) // c + 1 

c_num = f(a, b, c)
d_num = f(a, b, d)

cp = c
dp = d
mod = 1
while mod > 0:
    mod = cp % dp
    cp = dp
    dp = mod

cd_num =  f(a, b, (c * d) // cp)
print(b - a + 1 - c_num - d_num + cd_num)

Submission status: Accepted

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

c_f = (a + c - 1) // c
c_e =  b // c
d_f = (a + d - 1) // d
d_e =  b // d

cd = c * d // math.gcd(c, d)
c_d_num = b // cd - (a + cd - 1) // cd + 1

num = b - a + 1 - (c_e - c_f + 1 + d_e - d_f + 1 - c_d_num)
 
print(num)

Submission status: Accepted

Solution code:
a,b,c,d=list(map(int,input().split()))
import math
def yakusuu(n):
  return n//c+n//d-n//(c*d//math.gcd(c,d))


print(int(b-a+1-(yakusuu(b)-yakusuu(a-1))))

Submission status: Accepted

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

import numpy as np

# B
b = (B // C + B // D) - (B // np.lcm(C, D))
A = A - 1
a = (A // C + A // D) - (A // np.lcm(C, D))

print(B - A - (b - a))

Submission status: Accepted

Solution code:
import math

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

cd = c * d // math.gcd(c, d)

b_n = b // c + b // d - b // cd
a_n = a // c + a // d - a // cd
print((b - b_n) - (a - a_n))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import math
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


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


def find_target(x, c, d):
    num_c = x // c
    num_d = x // d
    lcm_cd = lcm(c, d)
    num_dip = x // lcm_cd
    return x - (num_c + num_d - num_dip)


def main():
    a, b, c, d = MI()
    target_in_a = find_target(a - 1, c, d)
    target_in_b = find_target(b, c, d)
    print(target_in_b - target_in_a)


main()

Submission status: Accepted

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

def div(z):
    p = (z//c) + (z//d) - (z//e)
    return p

x = a-1 - div(a-1)
y = b - div(b)
print(y-x)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import gcd
def main():
    a, b, c, d = map(int, input().split())
    if a == b:
        if a % c != 0 and a % d != 0:
            print(1)
            sys.exit()
        else:
            print(0)
            sys.exit()
    atob = b - a + 1
    divc = b // c - (a - 1) // c
    divd = b // d - (a - 1) // d
    cd = c * d // gcd(c, d)
    divcd = b // cd - (a - 1) // cd
    r = atob - divc - divd + divcd
    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# abc131_c.py
# https://atcoder.jp/contests/abc131/tasks/abc131_c

# C - Anti-Division /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 整数 A,B,C,Dが与えられます。A 以上 B 以下の整数のうち、C でも Dでも割り切れないものの個数を求めてください。

# 制約
#     1≤A≤B≤1018
#     1≤C,D≤109
#     入力はすべて整数である

# 入力
# 入力は以下の形式で標準入力から与えられる。
# A B C D

# 出力
# A以上 B 以下の整数のうち、C でも Dでも割り切れないものの個数を出力せよ。

# 入力例 1
# 4 9 2 3

# 出力例 1
# 2

# 5,7が条件を満たします。

# 入力例 2
# 10 40 6 8

# 出力例 2
# 23

# 入力例 3
# 314159265358979323 846264338327950288 419716939 937510582

# 出力例 3
# 532105071133627368


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    A, B, C, D = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    import math

    cd = (C*D) // math.gcd(C, D)
    ac = (A-1) // C
    ad = (A-1) // D
    acd = (A-1) // cd
    a = (A-1) - ac - ad + acd
    log(f'a=[{a}]')
    bc = B // C
    bd = B // D
    bcd = B // cd
    b = B - bc - bd + bcd
    log(f'b=[{b}]')

    result = b-a

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['4 9 2 3']
        lines_export = [2]
    if pattern == 2:
        lines_input = ['10 40 6 8']
        lines_export = [23]
    if pattern == 3:
        lines_input = ['314159265358979323 846264338327950288 419716939 937510582']
        lines_export = [532105071133627368]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    a, b, c, d = I2()
    #bまでのc,dの倍数 - a-1以下のc,dの倍数 重複分を加算
    cnt = b - a + 1
    cnt -= b//c
    cnt += (a-1)//c
    cnt -= b//d
    cnt += (a-1)//d
    cnt += b//(c*d//math.gcd(c,d))
    cnt -= (a-1)//(c*d//math.gcd(c,d))
    print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from math import gcd

a,b,c,d=nii()

a_c=(a-1)//c
b_c=b//c

a_d=(a-1)//d
b_d=b//d

lcm=(c*d)//gcd(c,d)
a_lcm=(a-1)//lcm
b_lcm=b//lcm

print((b-a+1)-(b_c-a_c)-(b_d-a_d)+(b_lcm-a_lcm))

Submission status: Accepted

Solution code:
from math import gcd

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

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

cd = lcm(c,d)
ab = b-a+1

print(ab-(b//c-(a-1)//c)-(b//d-(a-1)//d)+(b//cd-(a-1)//cd))

Submission status: Accepted

Solution code:
import math

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

a = A - 1
bn = B - B//C - B//D + (B//((C*D)//math.gcd(C,D)))
an = a - a//C - a//D + (a//((C*D)//math.gcd(C,D)))
print(bn - an)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
a,b,c,d = map(int, input().split())
e = c*d//math.gcd(c,d)
# CでもDでも割り切れない -> Cで割り切れない＋Dで割り切れない - CとDで割り切れない
xa = math.ceil(a/c)-1
xb = b//c
ya = math.ceil(a/d)-1
yb = b//d
za = math.ceil(a/e)-1
zb = b//e
ans = (b-a+1)-(xb-xa)-(yb-ya)+(zb-za)
if ans >=0:
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from math import gcd

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

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

def n_mul(c):
  if A%c==0 and B%c==0:return(B//c-A//c+1)
  elif A%c==0 and B%c!=0:return(B//c-A//c+1)
  elif A%c!=0 and B%c==0:return(B//c-A//c)
  else:return(B//c-A//c)

print(B-A+1-(n_mul(C)+n_mul(D)-n_mul(lcm)))

Submission status: Accepted

Solution code:
A,B,C,D =map(int,input().split())
x = C
y = D
while y>0:
    x,y = y,x%y
E = (C//x)*D
bc = B//C
bd = B//D
be = B//E
b = B-(bc+bd-be)
ac = (A-1)//C
ad = (A-1)//D
ae = (A-1)//E
a = A-1-(ac+ad-ae)
print(b-a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

A, B, C, D = mapint()
from math import gcd

m = C*D//gcd(C, D)
Ccnt = B//C-(A-1)//C
Dcnt = B//D -(A-1)//D
Mcnt = B//m - (A-1)//m

print((B-A)-(Ccnt+Dcnt-Mcnt)+1)

Submission status: Accepted

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

def calc(X, a, b):
    return X - (X // a + X // b - X // ((a * b) // gcd(a, b)))

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

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
import math
lcm = (c * d) // math.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:
import math
A,B,C,D=map(int,input().split())
E=C*D//math.gcd(C,D)
c=B//C-(A-1)//C
d=B//D-(A-1)//D
e=B//E-(A-1)//E
print(B-A+1-c-d+e)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import gcd
a, b, c, d = map(int, input().split())

x = b - b//c - b//d + b//(int(c*d/gcd(c, d)))
y = (a-1) - (a-1)//c - (a-1)//d + (a-1)//(int(c*d/gcd(c, d)))
print(int(x-y))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd

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

Submission status: Accepted

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

s = b - ((b//c)+(b//d)) + b//((c*d)//gcd(c,d))
t = (a-1) - (((a-1)//c)+((a-1)//d)) + (a-1)//((c*d)//gcd(c,d))
print(s-t)

Submission status: Accepted

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

E = C*D//math.gcd(C,D)
all = B - A + 1
Cmod = B//C - (A-1)//C
Dmod = B//D - (A-1)//D
CDmod = B//E - (A-1)//E

print(all - Cmod - Dmod + CDmod)

Submission status: Accepted

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

import math
g = math.gcd(c, d)
l = int(c * d / g)

less_b = b - (b // c + b // d - b // l)
less_a = (a-1) - ((a-1)//c + (a-1) // d - (a-1)//l)
print(less_b-less_a)

Submission status: Accepted

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

if C == 1 or D == 1:
    print(0)
    exit()

def check(A, B, x):
    return B//x - (A-1)//x

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

Submission status: Accepted

Solution code:
from fractions import gcd #最大公約数
A, B, C, D = map(int, input().split())
# (0~Bのうち, C,D,C*Dの倍数ではないものの数)　- (0~-Aのうち, C,D,C*Dの倍数ではないものの数)
lcm = C * D // gcd(C, D) #C,Dの最小公倍数
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // lcm
y = B - B // C - B // D + B // lcm
# (0~Bの数) - {(0~BのうちCで割り切れる数) + (0~BのうちDで割り切れる数) - (0~BのうちC,Dの最小公倍数で割り切れる数)}
print(y - x)

Submission status: Accepted

Solution code:
import math

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


def not_multiple_of_c_and_d(x: int, c: int, d: int):
    lcm_cd = c * d // math.gcd(c, d)
    c_no_baisu = x // c
    d_no_baisu = x // d
    cd_no_baisu = x // lcm_cd
    return x - (c_no_baisu + d_no_baisu - cd_no_baisu)


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

Submission status: Accepted

Solution code:
import math
def readinput():
    a,b,c,d=map(int,input().split())
    return a,b,c,d

def main(a,b,c,d):
    lcm=c*d//math.gcd(c,d)
    #print(lcm)
    return b-a+1 - ( b//c-(a-1)//c + b//d-(a-1)//d - ( b//lcm - (a-1)//lcm ) )


if __name__=='__main__':
    a,b,c,d=readinput()
    ans=main(a,b,c,d)
    print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

def f(x,p):
    return x//p

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

X=f(B,C)-f(A-1,C)
Y=f(B,D)-f(A-1,D)
Z=f(B,E)-f(A-1,E)
print(B-A+1-(X+Y-Z))

Submission status: Accepted

Solution code:
import math

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


def count(n, d):
    return n // d


c_dividable = count(B, C) - count(A-1, C)
d_dividable = count(B, D) - count(A-1, D)
cd = C*D // math.gcd(C, D)
cd_dividable = count(B, cd) - count(A-1, cd)

print((B-A+1) - (c_dividable+d_dividable-cd_dividable))

Submission status: Accepted

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