Problem:


Score : 300 points

Problem Statement

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

Constraints

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

1\leq C,D\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

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

Sample Input 1

4 9 2 3

Sample Output 1

2

5 and 7 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

23

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368



Sample input:
4 9 2 3


Sample output:
2

Submission status: Accepted

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

gcd = c
t = d
while t:
    gcd, t = t, gcd % t

lcm = c * d // gcd
e = b + 1 - a

dif += b // c - (a - 1) // c
dif += b // d - (a - 1) // d
plus += b // lcm - (a -1) // lcm

print(e - dif + plus)

Submission status: Accepted

Solution code:
#c.py
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
def lcm(a, b):
    return a * b // gcd(a,b)
a,b,c,d = map(int,input().split())
canC = int(b//c) -int((a-1)//c)
canD = int(b//d) - int((a-1)//d)
dbCD = int(b//lcm(c,d)) -int((a-1)//lcm(c,d))
print((b-a+1) -canC - canD + dbCD)

Submission status: Accepted

Solution code:
import sys
import fractions
import numpy as np

def hoge(A,B,g):
    min_r = A//g
    if A%g != 0:
        min_r += 1

    max_r = B//g

    return max_r - min_r + 1

if __name__ == '__main__' :
    A, B, C, D = list(map(int, input().split()))
    
    num_c = hoge(A,B,C)
    num_d = hoge(A,B,D)
    E = (C*D)//fractions.gcd(C,D)
    num_e = hoge(A,B,E)

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

Submission status: Accepted

Solution code:
A,B,C,D = map(int,input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
CD = lcm(C,D)
c_div = 0
d_div = 0
cd_div = 0
ans = 0
if A % C == 0:
    first_C = A
else:
    first_C = A + C -(A%C)
last_C = B -(B%C)
c_div = (last_C - first_C)//C + 1

if A % D == 0:
    first_D = A
else:
    first_D = A + D -(A%D)
last_D = B - (B%D)
d_div = (last_D - first_D)//D + 1

if A % CD == 0:
    first_CD =A
else:
    first_CD = A + CD -(A%CD)
last_CD = B -(B%CD)
cd_div = (last_CD - first_CD)//CD + 1

ans = c_div + d_div -cd_div
print(B-A+1-ans)

Submission status: Accepted

Solution code:
import fractions

num = input().split()
a, b, c, d = int(num[0])-1, int(num[1]), int(num[2]), int(num[3])

lcd = int(c*d/fractions.gcd(c, d))
warikire = (b//c-a//c)+(b//d-a//d)-(b//lcd-a//lcd)

print(int(b-a-warikire))

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
#最大公約数
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

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

c_div_a = (a-1) // c
c_div_all = b // c

d_div_a = (a-1) // d
d_div_all = b // d


cd_div_a = (a-1) // int( lcm(c, d) )
# print("cd_div_a", cd_div_a)
cd_div_all = b // int( lcm(c, d) )
# print("cd_div_all", cd_div_all)


div_a = c_div_a + d_div_a - cd_div_a
div_all = c_div_all + d_div_all - cd_div_all

print( (b - (a-1)) - (div_all - div_a) )

Submission status: Accepted

Solution code:
#C問題
import fractions
A, B, C, D = map(int,input().split())
if A%C ==0:
    count = 1 + B//C - A//C
else:
    count = B//C - A//C
if A%D ==0:
    count = 1 + B//D - A//D + count
else:
    count = B//D - A//D + count
lcm = C*D//fractions.gcd(C,D)
if A%lcm ==0:
    count = count - (1 + B//lcm - A//lcm)
else:
    count = count - (B//lcm - A//lcm)
print(B-A+1-count)

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
def pdw(n):
    i=2
    t=[]
    ta = t.append
    while i*i<=n:
        while n%i==0:
            n//=i
            ta(i)
        i+=1
    if n>1:ta(n)
    return t

#print(pdw(D))
#print(pdw(C))
bc = fractions.gcd(C,D)
lbc = C*D//bc
#print(lbc)
t = B - (B//C+B//D-B//lbc)
if A == 1:
    print(t)
else:
    p = A-1
    u = p - (p//C+p//D-p//lbc)
    print(t-u)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D=list(map(int, input().split()))
counter = 0
lcm = int((C*D)/fractions.gcd(C,D))
cda = (A-1)//C
dda = (A-1)//D
cdb = B//C
ddb = B//D
cdda = int((A-1)//lcm)
cddb = int(B//lcm)
counter = (cdb - cda) + (ddb - dda) - (cddb - cdda)
print(int(B-A+1-counter))

Submission status: Accepted

Solution code:
a,b,c,d = list(map(int,input().split()))
ans = 0
if b % c == 0:
    ans += b//c
else:
    ans += (b- (b%c)) //c

if (a-1) % c == 0:
    ans -= (a-1)//c
else:
    ans -= ((a-1)- ((a-1)%c)) //c

ans = int(ans)
if b % d == 0:
    ans += b//d
else:
    ans += (b- (b%d)) //d

if (a-1) % d == 0:
    ans -= (a-1)//d
else:
    ans -= ((a-1)- ((a-1)%d)) //d
ans = int(ans)
e = c*d

c_2 = c
d_2 = d
if (c_2< d_2):
    tmp = c_2
    c_2 = d_2
    d_2 = tmp
r = c_2 % d_2
while r != 0:
    c_2 = d_2
    d_2 = r
    r = c_2 % d_2
e = int(e //d_2)

ans2 = 0


if b % e == 0:
    ans2 += b//e
else:
    ans2 += (b- (b%e)) //e
if (a-1) % e == 0:
    ans2 -= (a-1)//e
else:
    ans2 -= ((a-1)- ((a-1)%e)) //e

sa = ans - ans2
print(int(b-a+1-sa))

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

# 0 => A-1 で割りきれる
cnt_c = (A-1) // C
cnt_d = (A-1) // D

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

cnt_a = cnt_c + cnt_d - cnt_cd

# 0 => Bで割りきれる
cnt_c2 = B // C
cnt_d2 = B // D
cnt_cd2 = B // lcm(C, D)

cnt_b = cnt_c2 + cnt_d2 - cnt_cd2

cnt_ab = cnt_b - cnt_a

cnt_n = B - A + 1

print(cnt_n - cnt_ab)

Submission status: Accepted

Solution code:
# coding: utf-8

import fractions

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

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

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

b_c = b // c
b_d = b // d
b_cd = b // lcm(c, d)


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

Submission status: Accepted

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

n = B - A + 1

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

if A == B:
  print(int(not( A%C==0 or A%D==0 )))
elif C != D:
  print( n- ( (B//C - (A-1)//C) + (B//D - (A-1)//D) - (B//CD - (A-1)//CD) ) )
else:
  print( n- ( (B//C - (A-1)//C) ) )

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

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

b_num = b - b//c - b//d + b//lcm
a_num = (a-1) - (a-1)//c - (a-1)//d + (a-1)//lcm


ans = b_num - a_num

print(ans)

Submission status: Accepted

Solution code:

import fractions

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


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

if A%C==0:
    nC_initial=A//C
else:
    nC_initial=A//C+1
    
if A%D==0:
    nD_initial=A//D
else:
    nD_initial=A//D+1

    
if A%E==0:
    nE_initial=A//E
else:
    nE_initial=A//E+1
    
nC_final=B//C
nD_final=B//D
nE_final=B//E
if nC_final<nC_initial:
    nC_final=nC_initial
if nD_final<nD_initial:
    nD_final=nD_initial
if nE_final<nE_initial:
    nE_final=nE_initial
nc=(nC_final-nC_initial+1)
nd=(nD_final-nD_initial+1)
ne=(nE_final-nE_initial+1)
if B<C:
    nc=0
    ne=0
if B<D:
    nd=0
    ne=0
if B<E:
    ne=0


#print(ans,nC_initial,nC_final,nD_initial,nD_final, nE_initial,nE_final)
#print(ans,nc,nd,ne)
print(ans-nc-nd+ne)

Submission status: Accepted

Solution code:
mod = 10**9+7
def gcd(c,d):
    #c<d
    if d%c == 0:
        return c
    else:
        return gcd(d%c,c)

def main():
    a,b,c,d=map(int,input().split(' '))
    c,d=sorted([c,d])
    lmc = int(c*d/gcd(c,d))
    e = a-1
    ans = int((b-a+1)-(b//c + b//d - b//lmc -1*(e//c + e//d - e//lmc)))
    print(ans)

main()

Submission status: Accepted

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) 
    
e=(c*d)//gcd(c,d)
ans3=b//e-(a-1)//e

ans=b-a+1-ans1-ans2+ans3

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

a, b, c, d = map(int,input().split())
cn_l, cn_r, cn_d = 0,0,0
l_list = []
r_list = []
if a%c == 0:
    start_l = a//c
else:
    start_l = a//c+1
# print('left')
cn_l = b//c+1 - start_l
# for i in range(start_l, b//c+1):
#     l_list.append(c*i)
#     cn_l += 1
if a%d == 0:
    start_r = a//d
else:
    start_r = a//d+1
# print('right')
cn_r = b//d+1 - start_r
# for i in range(start_r, b//d+1):
#     r_list.append(d*i)
#     cn_r += 1
# print(cn_l, cn_r)
# for val in l_list:
#     if val in r_list:
#         cn_d +=1
def lcm(x, y):
    return (x * y) // gcd(x, y)
lcm = lcm(c,d)
if a%lcm == 0:
    start_d = a//lcm
else:
    start_d = a//lcm+1
cn_d = b//lcm+1 - start_d
n = b-a+1
print(n-(cn_l+cn_r-cn_d))

Submission status: Accepted

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

cd = c*d // fr.gcd(c,d)
a_ = ((a-1)//c + (a-1)//d) - ((a-1)//cd)
b_ = (b//c + b//d) - (b//cd)
s_ = b_- a_
print(s-s_)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

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

	E = lcm(C, D)
	if A == B:
		if A % C == 0 or A % D == 0:
			print(0)
			sys.exit()
		else:
			print(1)
			sys.exit()

	if C == D or C % D == 0 or D % C == 0:
		tmp_C2 = B // C
		tmp_C2ama = B % C

		tmp_C1 = A // C
		tmp_C1ama = A % C

		tmp = (tmp_C2-tmp_C1)

		tmp2 = 0
		if tmp_C1ama == 0:
			tmp2 -=1

		ans = B-A-tmp+1+tmp2
		print(ans)
		sys.exit()

	tmp_C2 = B // C
	tmp_C2ama = B % C
	tmp_D2 = B // D
	tmp_D2ama = B % D
	tmp_C1 = A // C
	tmp_C1ama = A % C
	tmp_D1 = A // D
	tmp_D1ama = A % D

	tmp_E2 = B // E
	tmp_E2ama = B % E
	tmp_E1 = A // E
	tmp_E1ama = A % E

	tmp = (tmp_C2+tmp_D2)-(tmp_C1+tmp_D1)

	tmp2 = 0
	if tmp_C1ama == 0:
		tmp2 -=1
	if tmp_D1ama == 0:
		tmp2 -=1
	if tmp_E1ama == 0:
		tmp2 += 1

	#print(E)

	ans = B-A-tmp+1+(tmp_E2-tmp_E1)+tmp2

	print(ans)

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

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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = (int(x) for x in input().split())
x = (B // C) - ((A - 1) // C)
x += (B // D) - ((A - 1) // D)
lcm = (C * D) // fractions.gcd(C, D)
x -= (B // lcm) - ((A - 1) // lcm)
print((B - A + 1) - x)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from decimal import *

A, B, C, D = list(map(Decimal, stdin.readline().split()))
cd = C * D / Decimal(str(fractions.gcd(C,D)))

Nc = Decimal(B / C).quantize(Decimal("0"), rounding=ROUND_FLOOR) - Decimal(A / C).quantize(Decimal("0"), rounding=ROUND_CEILING) + Decimal("1")
Nd = Decimal(B / D).quantize(Decimal("0"), rounding=ROUND_FLOOR) - Decimal(A / D).quantize(Decimal("0"), rounding=ROUND_CEILING) + Decimal("1")
Ncd = Decimal(B / cd).quantize(Decimal("0"), rounding=ROUND_FLOOR) - Decimal(A / cd).quantize(Decimal("0"), rounding=ROUND_CEILING) + Decimal("1")

print(B-A+Decimal("1")-(Nc+Nd-Ncd))

Submission status: Accepted

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

lcm = lcm(C, D)
# A
Ax = A // lcm
Ay = A // C
Az = A // D
AA = Ay + Az -Ax
a = A - AA
# B
Bx = B // lcm
By = B // C
Bz = B // D
BB = By + Bz -Bx
b = B - BB

print(b - a)

Submission status: Accepted

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

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

def count(a, b, q):
  _a = min(a, b)
  _b = max(a, b)
  if a % q == 0:
    return _b // q - _a // q + 1
  else:
    return _b // q - _a // q

A, B, C, D = list(map(int, input().split()))
lcm = lcm(max(C, D), min(C, D))
print((B - A + 1) - count(A, B, C) - count(A, B, D) + count(A, B, lcm))

Submission status: Accepted

Solution code:
import fractions
list = list(map(int,input().split()))
x = (list[2] * list[3]) // fractions.gcd(list[2], list[3])
p = (list[0]-1)//list[2]
q = list[1]//list[2]
r = (list[0]-1)//list[3]
s = list[1]//list[3]
t = (list[0]-1)//x
u = list[1]//x
l = list[1]-list[0]+1
print(l+p-q+r-s-t+u)

Submission status: Accepted

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


def calc(x, y, z):
    ny = x // y
    nz = x // z
    nyz = x // (y * z // yaku(y ,z))

    #print(ny, nz, nyz)
    #print(x - ny - nz + nyz)

    return (x - ny - nz + nyz)


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

rtn = calc(b,c,d) - calc(a-1,c,d)

print(int(rtn))

Submission status: Accepted

Solution code:
a, b, c, d = (int(x) for x in input().split())
c_num = b//c - (a - 1)//c
d_num = b//d - (a - 1)//d

big = max(c, d)
small = min(c, d)

while big % small != 0:
    tmp = small
    small = big % small
    big = tmp

x = c * d // small

x_num = b // x - (a - 1) // x

print(int(b - a + 1 - (c_num + d_num - x_num)))

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D = map(int,input().split())
l = B-A+1
lcm = C//gcd(C,D)*D
b = B//C - A//C
d = B//D - A//D
lc = B//lcm - A//lcm
a1 = l-l//C-l//D+l//lcm
a2 = l-b-d+lc
print(min(a1,a2))

Submission status: Accepted

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

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

A = A - 1
a = B // C
b = B // D
c = B // (C*D // gcd(C,D))
d = A // C
e = A // D
f = A // (C*D // gcd(C,D))
print(B - (a + b - c) - (A - (d + e - f)))

Submission status: Accepted

Solution code:
from fractions import gcd

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


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

# 変数C の倍数が A, B 区間内に存在しうる数
Ccount = (B // C) - ((A - 1) // C)

# 変数D の倍数が A, B 区間内に存在しうる数
Dcount = (B // D) - ((A - 1) // D)

# 変数C, D の最小公倍数が A, B 区間内に存在しうる数
CDcross = (B // lcm(C, D)) - ((A - 1) // lcm(C, D))

# Cが存在しうる数と Dが存在しうる数を引き、重複する（＝最小公倍数）数は引きすぎなので戻す
print((B-A+1) - ((Ccount + Dcount - CDcross)))

Submission status: Accepted

Solution code:
import fractions

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

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

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

Submission status: Accepted

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

# n_c = 0
# n_d = 0
# n_cd = 0
# for i in range(A,B+1):
#     if(i % C == 0):
#         n_c = i // C
#     n_d = i // D
#     n_cd = i//(C*D)

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

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

if(A%C == 0):
    n_c += 1
if(A%D==0):
    n_d += 1
if(A%CD==0):
    n_cd += 1


if (max(C,D)%min(C,D) == 0):
    ans = (B-A+1) - max(n_c, n_d)
else:
    ans = (B-A + 1) - (n_c + n_d - n_cd)

# print(n_c)
# print(n_d)
# print(n_cd)

print(ans)

Submission status: Accepted

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

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 z

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

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

Submission status: Accepted

Solution code:
import fractions

def div(a,b,c):
    val=b//c-(a-1)//c
    return val

A,B,C,D=map(int,input().split())
numC=div(A,B,C)
numD=div(A,B,D)
lcm=int(C*D/(fractions.gcd(C,D)))
numCD=div(A,B,lcm)
ans=B-A+1-numC-numD+numCD
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

s1 = A - ((A//C) + (A//D) - (A//l))
s2 = B - ((B//C) + (B//D) - (B//l))
s3 = 0

if A%C != 0 and A%D != 0:
    s3 = 1

print(s2-s1 + s3)

Submission status: Accepted

Solution code:
A,B,C,D = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

#Python -3.4
from fractions import gcd
#a=77
#b=121
#print(a,b,gcd(a,b))

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


a=A//C
b=B//C

c=0
for i in range(a,b+1):
	if A<=(i*C)<=B:
		c = b-i+1
		break
c=max(0,c)

#print("C,a,b,c",C,a,b,c)

a=A//D
b=B//D
d=0
for i in range(a,b+1):
	if A<=(i*D)<=B:
		d = b-i+1
		break
d=max(0,d)

#print("D,a,b,d",D,a,b,d)

E=lcm(C,D)

a=A//E
b=B//E
e=0
for i in range(a,b+1):
	if A<=(i*E)<=B:
		e = b-i+1
		break
e=max(0,e)

#print("E,a,b,e",E,a,b,e)

ans= B-A+1-(c + d - e)

print(ans)

Submission status: Accepted

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

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

cd = lcm(c, d)

# cの倍数とdの倍数の個数を数える
# cの倍数dの倍数の個数を引く
ca = ((a-1) // c)
# print(ca)
cb = (b // c)
# print(cb)
tmp_c = cb - ca

da = (a // d)
# print(da)
db = (b // d)
# print(db)
tmp_d = db - da

cda = (a // cd)
# print(cda)
cdb = (b // cd)
# print(cdb)
tmp_cd = cdb - cda
ans = b - a + 1 - (tmp_c + tmp_d - tmp_cd)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# n = int(sys.stdin.readline())
# a, b = map(int, sys.stdin.readline().split())
# c = list(map(int, sys.stdin.readline().split()))
# s = [list(map(int,list(sys.stdin.readline()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a = 100
# b = 0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋め, 小数点出力桁指定時のときの出力
# 000100-0.987654

import math
import sys
import itertools
import queue
from functools import reduce
from fractions import gcd

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

mod = 1000000007

if __name__ == "__main__":
    A, B, C, D = map(int, sys.stdin.readline().split())
    A = A - 1
    c_div = int(B // C)
    d_div = int(B // D)
    cd_div = int(B // lcm(C, D))

    not_div1 = B - (c_div + d_div -cd_div)

    c_div = int(A // C)
    d_div = int(A // D)
    cd_div = int(A // lcm(C, D))

    not_div2 = A - (c_div + d_div -cd_div)

    print(not_div1 - not_div2)

Submission status: Accepted

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

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

g = gcd(c, d)
print(s - (dev(c) + dev(d) - dev(c * d // g)))

Submission status: Accepted

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

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

ac = (a-1) // c
ad = (a-1) // d
ae = (a-1) // e
bc = b // c
bd = b // d
be = b // e
print((b-a+1) - ((bc + bd - be) - (ac + ad - ae)))

Submission status: Accepted

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

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


countC = B // C - A // C
if A % C == 0:
    countC += 1
countD = B // D - A // D
if A % D == 0:
    countD += 1
s = gcd(C, D)
countCD = B // C // (D // s) - A // C // (D // s)
temp = A / C / (D // s)
if temp == int(temp):
    countCD += 1

res = (B - A + 1 - countC - countD + countCD)
if res < 0:
    res = 0
print(res)

Submission status: Accepted

Solution code:
import numpy as np
import math

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

a, b, c, d = [int(i) for i in input().split()]
#
#num = np.arange(b - a + 1) + a
#
#if b < c and b < d:
#    print('0')
#    exit(0)
#
#m = min(c, d)
#div = max(c, d)
#tmp = []
#div = num[0] // div + div
#index = 0
#while True:
#    if n[index] % div != 0:
#        if index + div >
#        tmp += range(n[index], n[index])
#        index += 1
#    else:
#        index += div
#
#tmp = np.array(tmp)
#print(tmp[tmp % m == 0].shape[0])


size = b - a + 1
cd = int(c * d // gcd(c, d))
c_num_a = a // c
d_num_a = a // d
cd_num_a = a // cd
c_num_b = b // c
d_num_b = b // d
cd_num_b = b // cd

c_num = c_num_b - c_num_a
d_num = d_num_b - d_num_a
cd_num = cd_num_b - cd_num_a

if a % c == 0:
    c_num += 1
if a % d == 0:
    d_num += 1
if a % cd == 0:
    cd_num += 1

print(size - c_num - d_num + cd_num)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,collections,math,random,fractions;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())

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

a,b,c,d = Is()
mc = b//c - (a-1)//c
md = b//d - (a-1)//d
mincom = lcm(c,d)
mcd = b//(mincom) - (a-1)//(mincom)
ans = b-a+1 - (mc + md - mcd)
#print(mc,md,mcd)
print(ans)

Submission status: Accepted

Solution code:
import fractions

def calcA(a, b):
    ans = a / b
    if ans.is_integer():
        return a // b
    else:
        return a // b + 1 


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

a1 = calcA(a,c)

a2 = b // c
a3 = a2 - a1 + 1

b1 = calcA(a,d)

b2 = b // d
b3 = b2 - b1 + 1

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

x1 = calcA(a,x)
x2 = b // x
x3 = x2 - x1 + 1

p = b - a + 1
q = a3 + b3 - x3

print(p - q)

Submission status: Accepted

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

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

def func(num, A, B):
    if A % num == 0:
        return B // num - A // num + 1
    else:
        return B // num - A // num

first = func(C, A, B)
second = func(D, A, B)
third = func(LCM, A, B)

total = first + second - third

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

Submission status: Accepted

Solution code:
import sys
import fractions

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

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

count = b - a + 1 -1* (b // c) + (a-1) // c  -1*( b // d )+ (a-1) // d  + b // lcm -1*( (a-1) // lcm)

if count < 0 :
    count = 0

print(count)

Submission status: Accepted

Solution code:
import fractions
RangeMin, RangeMax, valA, valB = map(int, input().split())

RangeMin -= 1
valC = int(valA * valB / fractions.gcd(valA, valB))
ansList = []



for Range in [RangeMin, RangeMax] :
  ans1 = 0
  ans1 += Range // valA
  ans1 += Range // valB
  ans1 -= Range // valC
  ansList.append(ans1)

ans = ansList[1] - ansList[0]
ans = RangeMax - RangeMin - ans

print(ans)

Submission status: Accepted

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


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


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

e=lcm(c,d)


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


ans_h=k(b,c)+k(b,d)-k(b,e)-(k(a-1,c)+k(a-1,d)-k(a-1,e))

print(b-a+1-ans_h)

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())
g = lcm(c, d)

alpha_c = a % c
count_c = (b - a + alpha_c) // c
if alpha_c == 0:
    count_c += 1
alpha_d = a % d
count_d = (b - a + alpha_d) // d
if alpha_d == 0:
    count_d += 1
alpha_g = a % g
count_g = (b - a + alpha_g) // g
if alpha_g == 0:
    count_g += 1

s = b - a + 1 - count_c - count_d + count_g

print(s)

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 = [int(x) for x in input().split(' ')]
a = (B - A + 1) 
b = ((B // C) - ((A-1) // C))
c = ((B // D) - ((A-1) // D))
CD = lcm(C,D)
d = ((B // (CD)) - ((A-1) // (CD)))
q = a - b - c + d
print(q)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
def amari(a):
    return a - a // C - a // D + a // L
A, B, C, D = map(int,input().split())
L = (C * D) // fractions.gcd(C, D)
E = amari(L)
K = B - A + 1
counter = amari(B - K // L * L) - amari(A - 1)
print((K // L) * E + counter)

Submission status: Accepted

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

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

c_num = b//c - (a-1)//c
d_num = b//d - (a-1)//d
cd_num = b//lcm(c,d) - (a-1)//lcm(c,d)

print(nums-(c_num+d_num-cd_num))

Submission status: Accepted

Solution code:
import fractions
a,b,c,d = map(int,input().split())
lcm_cd = int(c*d / fractions.gcd(c,d))
if a%c==0:
  tc = b//c - a//c + 1
else:
  tc = b//c - a//c
if a%d==0:
  td = b//d - a//d + 1
else:
  td = b//d - a//d
if a%(lcm_cd)==0:
  tcd = b//(lcm_cd) - a//(lcm_cd) + 1
else:
  tcd = b//(lcm_cd) - a//(lcm_cd)

print(b-a+1-tc-td+tcd)

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
  
x = (b // c) - (a // c)
if a % c == 0:
  x += 1
y = (b // d) - (a // d)
if a % d == 0:
  y += 1

lcm = c * d // gcd(c, d)  
z = (b // lcm) - (a // lcm)
if a % lcm == 0:
  z += 1

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())
AC = (A - 1) // C
AD = (A - 1) // D
BC = B // C
BD = B // D
BCD = B // lcm(C, D)
ACD = (A - 1) // lcm(C, D)
tmp = (BC + BD) - (AC + AD) - (BCD - ACD)
ans = (B - A + 1) - tmp
print(ans)

Submission status: Accepted

Solution code:
A,B,C,D = map(int, input().split())
ma=B
mi=A-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)

E=lcm(C,D)

ta=ma//C
tb=mi//C
h=ta-tb

tc=ma//D
td=mi//D
i=tc-td

te=ma//E
tf=mi//E
j=te-tf

wareru=h+i-j
kotae=ma-mi-wareru
print(kotae)

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())
cnt = 0
cc = c
dd = d
cd = lcm(c,d)
cdcd = lcm(c,d)

if a % c == 0:
  minc = a // c
else:
  minc = a // c + 1
maxc = b // c
if a < c:
  lenc = maxc
else:
  lenc = maxc - minc + 1
  
if a % d == 0:
  mind = a // d
else:
  mind = a // d + 1
maxd = b // d
if a < d:
  lend = maxd
else:
  lend = maxd - mind + 1

if a % cd == 0:
  mincd = a // cd
else:
  mincd = a // cd + 1
maxcd = b // cd
if a < cd:
  lencd = maxcd
else:
  lencd = maxcd - mincd + 1
#print(lenc)
#print(lend)
#print(lencd)
print(b-a+1-lenc-lend+lencd)

Submission status: Accepted

Solution code:
import sys
import fractions

def input():
    return sys.stdin.readline().rstrip()

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

if __name__ == "__main__":
    a, b, c, d = map(int, input().split())

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

    print((b - a + 1) - (y - x))

Submission status: Accepted

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

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

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

def getDivNum(n, c, d):
  return n // c + n // d - (n // lcm(c, d))

print(B - A - getDivNum(B, C, D) + getDivNum(A-1, C, D) + 1)

Submission status: Accepted

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

if c!=d:
    
    
    sma=min(c,d)
    big=max(c,d)
    
    while sma!=0 :
        cal=big%sma
        big=sma
        sma=cal
    
    euc=big
    ggg=c*d//euc
    
    #print(euc,ggg)
    
    def  cnt(n,ggg,c,d):
        exc=ggg//c + ggg//d
        if c<ggg or d<ggg:
            exc-=1
        ret=exc*(n//ggg)
        #print(ggg,exc,ret)
        remain=n%ggg
        ret+= remain//c + remain//d
        return ret
    
    #print(cnt(b,ggg,c,d))
    #print(cnt(a-1,ggg,c,d))
    
    jog=cnt(b,ggg,c,d)-cnt(a-1,ggg,c,d)
    
    ans=(b-a+1)-jog
    
    print(ans)
    
else:
    jog=(b//c) -((a-1)//c)
    print(b-a+1-jog)

Submission status: Accepted

Solution code:
import fractions
A,B,C,D = map(int,input().split())
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
syou = (A-1) - (A-1)//C - (A-1)//D + (A-1)//lcm(C,D)
dai = B - B//C - B//D + B//lcm(C,D)
ans = dai - syou
print(ans)

Submission status: Accepted

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

def EA(X,Y):
    if X%Y==0:
        return Y
    
    return EA(Y,X%Y)

if C>D:
    CD=int(C/EA(C,D))*D
else:
    CD=int(C/EA(D,C))*D

A-=1

print(int(B-A-(B//C+B//D-B//CD-(A//C+A//D-A//CD))))

Submission status: Accepted

Solution code:
import platform
ver = platform.python_version_tuple()
if int(ver[1]) < 5:
    from fractions import gcd
else:
    from math import gcd
from sys import stdin

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

    lcm = lambda x, y: x * y // gcd(x, y)
    n = 0
    for a, b, x in ((A, B, C), (A, B, D)):
        if a % x:
            n += b // x - a // x
        else:
            n += b // x - (a // x - 1)

    lcm_ = lcm(C, D)
    if a % lcm_:
        n -= b // lcm_ - a // lcm_
    else:
        n -= b // lcm_ - (a // lcm_ - 1)

    print(B - A + 1 - n)

input = lambda: stdin.readline()
main()

Submission status: Accepted

Solution code:
#coding:utf-8
a,b,c,d = map(int,input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)
def func(start,end,n):
    ans = (end-start+1)//n
    bonus = (end-start+1)%n
    #print (ans,((start // n + 1) * n),start + bonus - 1)
    
    if ((start // n + 1) * n)  <= (start + bonus - 1):
        ans += 1
    #print (ans)
    return ans
cnt_c = func(a,b,c)
cnt_d = func(a,b,d)
cnt_cd = func(a,b,lcm(c,d))
print (b-a-(cnt_c + cnt_d - cnt_cd)+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())

sub = B - A + 1
cDivNum = (B//C) - ((A-1)//C)
dDivNum = (B//D) - ((A-1)//D)
cdDivNum = (B//lcm(C,D)) - ((A-1)//lcm(C,D))

#print(sub,cDivNum,dDivNum,cdDivNum)
print(sub - (cDivNum+dDivNum-cdDivNum))

Submission status: Accepted

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

A, B, C, D = map(int, input().split())
divC = B // C - (A-1) // C
divD = B // D - (A-1) // D
divCD = B // ((C*D)//euc(C, D)) - (A-1) // ((C*D)//euc(C, D))
print((B-A+1) - divC - divD + divCD)