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:
import math
def gcd(a,b):
  if a < b:
     a,b = b,a
  c = a%b
  if c == 0:
    return b
  return gcd(b,c)

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

Submission status: Accepted

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

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

def under_div(A, C, D):
    lcm = C*D//gcd(C, D)
    return A//C+A//D-A//lcm

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

Submission status: Accepted

Solution code:
#n=int(input())
a,b,c,d=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
import fractions
lcm=(c*d)//fractions.gcd(c,d)#最小公倍数

brng=b-(b//c+b//d)+b//lcm
arng=(a-1)-((a-1)//c+(a-1)//d)+(a-1)//lcm
ans=brng-arng
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    c=a%b
    if c==0:
        return b
    return gcd(b,c)
A,B,C,D=map(int,input().split())

nc=B//C-(A-1)//C
nd=B//D-(A-1)//D
cd=int(C*D/gcd(C,D))
ncd=B//cd-(A-1)//cd
print(B-A+1-nc-nd+ncd)

Submission status: Accepted

Solution code:
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    c=a%b
    if c==0:
        return b
    return gcd(b,c)
A,B,C,D=map(int,input().split())
if A%C==0:
    #nc=int(B/C)-int(A/C)+1
    nc=B//C-A//C+1
else:
    #nc=int(B/C)-int(A/C)
    nc=B//C-A//C
if A%D==0:
    #nd=int(B/C)-int(A/C)+1
    #nd=int(B/D)-int(A/D)+1
    nd=B//D-A//D+1
else:
    #nd=int(B/D)-int(A/D)
    nd=B//D-A//D
cd=int(C*D/gcd(C,D))
if A%cd==0:
    #ncd=int(B/cd)-int(A/cd)+1
    ncd=B//cd-A//cd+1
else:
    #ncd=int(B/cd)-int(A/cd)
    ncd=B//cd-A//cd
#print("nc,nd,ncd",nc,nd,ncd)
print(B-A+1-nc-nd+ncd)

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 int(a*b / gcd(a,b))
X = A-B
Y = lcm(C,D)
i = B//C-(A-1)//C
j = B//D-(A-1)//D
k = B//Y-(A-1)//Y
print(int(B-A+1-(i+j-k)))

Submission status: Accepted

Solution code:
import itertools as it
import collections as col
import fractions
from functools import reduce

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

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def ppp(c,d):
	while c % d != 0:
		nc = d
		nd = c % d
		c,d = nc, nd
	return d

def main():
	a, b, c, d = IN()
	cad=(c*d)//ppp(c,d)
	
	
	all_num=b-a+1
	can_c=(b//c) - ((a-1)//c)
	can_d = (b//d) - ((a-1)//d)
	can_c_and_d = (b//(cad)) - ((a-1)//(cad))
	ret = all_num-can_c-can_d+can_c_and_d
	#pa((can_c,can_d,can_c_and_d,all_num))
	print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

c = C
d = D

gcd = 0
while gcd == 0:
  if c > d:
    k = c
    c = d
    d = k # 必ず c <= d になる
  if d%c == 0:
    gcd = c
  else:
    d = d%c

# 最小公倍数（lcm）
lcm = int(C*D/gcd)

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

Submission status: Accepted

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

from fractions import gcd

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

ac = (a - 1) // c
ad = (a - 1) // d
acd = (a - 1) // lcm(c, d)
x = (a - 1) - ac - ad + acd

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

ans = y - x
print(ans)

Submission status: Accepted

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

def f(n):
    if n==0:
        return 0
    else:
        return n-n//c-n//d+n//(c*d//fractions.gcd(c,d))

print(f(b)-f(a-1))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

lcm = lambda x, y: x * y // gcd(x, y)
a -= 1
ans = b - (b // c + b // d - b // lcm(c, d)) - a + (a // c + a // d - a // lcm(c, d))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def count_divisible_by(n, start, end):
    return end // n - (start - 1) // n

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

lcm = c * d // gcd(c, d)
print(b-a+1 - count_divisible_by(c, a, b) - count_divisible_by(d, a, b) + count_divisible_by(lcm, a, b))

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())
d1=b//c
d2=b//d
d3=b//lcm(c,d)

d4=(a-1)//c
d5=(a-1)//d
d6=(a-1)//lcm(c,d)

ansb=b-(d1+d2-d3)
ansa=a-1-(d4+d5-d6)
print(ansb-ansa)

Submission status: Accepted

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

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

def count(num, a, b):
    return int(num - num//a - num//b + num//lcm(a,b))

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

Submission status: Accepted

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

l = c*d // gcd(c, d)
x = (a-1) - (a-1)// c - (a-1) // d + (a-1) // 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())
g = c*d//gcd(c, d)
print(b-a+1 - b//c-b//d+b//g + (a-1)//c+(a-1)//d-(a-1)//g)

Submission status: Accepted

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

def div(x,y,z):
    x_r = x % z
    y_r = z - y % z
    tmp = ((y + y_r) - (x - x_r)) // z + 1
    if x_r != 0:
        tmp -= 1
    if y_r != 0:
        tmp -= 1
    return tmp

print(b-a+1-(div(a,b,c)+div(a,b,d)-div(a,b,c*d//fractions.gcd(c,d))))

Submission status: Accepted

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

def anti_div(a,b,c):
    aa = (a-1) - (a-1) // c
    bb = b - b // c
    return bb - aa

# c,dの最小公倍数を求める
# l = c*d / gcd
#lcd = c // math.gcd(c,d) * d
lcd = c // fractions.gcd(c,d) * d

ans = anti_div(a,b,c) + anti_div(a,b,d) - anti_div(a,b,lcd)
print(ans)

Submission status: Accepted

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

    def lcm(v1, v2):
        v3 = v1 % v2
        if v3 == 0:
            return v2
        return lcm(v2, v3)

    def gcd(v1, v2):
        return v1 * v2 // lcm(v1, v2)

    count = B - (A - 1)

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

    CD = gcd(C, D)
    cd = B // CD - (A - 1) // CD

    print(count - c - d + cd)


main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import os, sys, re, math, queue

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

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

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

lc = lcm(C,D)
tmp = B // C - (A-1) // C
tmp += B // D - (A-1) // D
tmp -= (B // lc - (A-1) // lc)
print(B-A+1-tmp)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from fractions import gcd

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

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

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import os, sys, re, math

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) = [int(n) for n in input().split()]

minC = (A + (C - 1)) // C
maxC = B // C

minD = (A + (D - 1)) // D
maxD = B // D

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

countC = maxC - minC + 1
countD = maxD - minD + 1
countCD = maxCD - minCD + 1

print(B - A - (countC + countD - countCD) + 1)

Submission status: Accepted

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

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

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

def counter(division):
    a = A // division
    if A % division == 0:
        a -= 1
    b = B // division
    return b - a

c = counter(C)
d = counter(D)
cd = counter(lcm(C , D))
ret = B - A + 1 - c - d + cd
print(ret)

Submission status: Accepted

Solution code:
a, b, c, d = list(map(int, input().split(' ')))
a = a - 1
def gcd(a, b):
    return b if a % b == 0 else gcd(b, a%b)

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

right_c = b // c
right_d = b // d
right = b - right_c - right_d + (b // (cd))
left_c = a // c
left_d = a // d
left = a - left_c - left_d + (a // (cd))
print(right - left)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import floor
from fractions import gcd

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

bc = B // C
bd = B // D
bcd = B // lcm

ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) // lcm

ans = B-bc-bd+bcd-(A-1-ac-ad+acd)
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    A,B,C,D=MI()
    A-=1
    B_cnt = B-(B//C+B//D-B//lcm(C,D))
    A_cnt = A-(A//C+A//D-A//lcm(C,D))
    print(B_cnt-A_cnt)
if __name__ == '__main__':
    main()

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

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

ans = b_num - a_num

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        x, y = y, x % y
    return x

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

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

num_C = b // c - (a - 1) // c  #約数にCを持つものの個数
num_D = b // d - (a - 1) // d  #約数にDを持つものの個数
num_CD = b // lcm(c, d) - (a - 1) // lcm(c, d)
#print(num_C, num_D, num_CD)
ans = (b - a + 1) - num_C - num_D + num_CD
print(ans)

Submission status: Accepted

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

import fractions

def f(N):
    red = N//C
    red += N//D
    X = (C * D // fractions.gcd(C, D))
    red -= N//X
    return N - red

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions

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

A,B,C,D=map(int,input().split())
E=B-A+1
F=B//C-(A-1)//C
G=B//D-(A-1)//D
H=B//lcm(C,D)-(A-1)//lcm(C,D)
count=E-F-G+H
print(count)

Submission status: Accepted

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


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


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

ans = b - a + 1
ans -= (div_c + div_d) - div_e

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

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

Submission status: Accepted

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

a,b,c,d = map(int,input().split())
lcm = (c*d) // gcd(c, d)
ans = b - a + 1
cdiv = b // c - (a-1) // c
ddiv = b // d - (a-1) // d
cddiv = b // lcm - (a-1) // lcm
#print(ans, cdiv, ddiv, cddiv, lcm)
ans -= cdiv + ddiv - cddiv
print(ans)

Submission status: Accepted

Solution code:
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)

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

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    a,b,c,d=map(int,input().split())
    a-=1
    e=a-a//c-a//d+a//lcm(c,d)
    f=b-b//c-b//d+b//lcm(c,d)
    print(f-e)
if __name__=="__main__":
    main()

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

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)
a1=(a-1)//c
a2=b//c
b1=(a-1)//d
b2=b//d
new_lcm=lcm(c,d)
c1=(a-1)//new_lcm
c2=b//new_lcm
print((b-a)+1-((a2-a1)+(b2-b1))+(c2-c1))
#print(a1,a2,b1,b2,c1,c2)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
a, b, c, d = map(int, input().split())
x, y = c, d
if x<y: x, y = y, x
while y: x, y = y, x%y
lcm = c*d//x

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

Submission status: Accepted

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

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

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

    def f(x):
        p = x//c
        q = x//d
        r = x//lcm(c, d)
        return x - p - q + r

    print(f(b) - f(a-1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def lcm(c, d):
    c, d = max(c, d), min(c, d)
    cd = c * d
    while c % d > 0:
        c, d = d, c % d
    return cd // d

def solve():
    A, B, C, D = map(int, input().split())
    cd = lcm(C, D)
    divC = B // C - (A - 1) // C
    divD = B // D - (A - 1) // D
    divCD = B // cd - (A - 1) // cd
    print((B - A + 1) - (divC + divD - divCD))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import fractions

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

# 全体の数 - (Cで割れる数 + Dで割れる数 - CとDで割れる数)
all_count = B-A+1

# 区間内でAで割れる数 -> 1からDまで割れる数 - 1からCまで割れる数？？？？
# 2で考えると       1 to 13 は 2,4,6,8,10,12の6つ 13//2
#                  1 to 5  は 2,4 の2つ 5//2 
#                  5 to 13 は 6,8,10,12 の4つ
#                  1 to 6  は 2,4,6
#                  6 to 13 は 6,8,10,12 の4つ 6は重複カウントなので、、、

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

# 1からA'まで'で割れる数
C_A_count = (A-1) // C
D_A_count = (A-1) // D
G_A_count = (A-1) // G

# 1からBで割れる数
C_B_count = B // C
D_B_count = B // D
G_B_count = B // G

C_count = C_B_count - C_A_count
D_count = D_B_count - D_A_count
G_count = G_B_count - G_A_count

print(all_count - (C_count + D_count - G_count))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    a,b,c,d=mis()
    lcm = c*d//gcd(c,d)
    print((b - (a-1)) - (b//c - (a-1)//c) - (b//d - (a-1)//d) + (b//lcm - (a-1)//lcm))

main()

Submission status: Accepted

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

from fractions import gcd
total = B - A + 1
c_multiples = B // C + 1 - (A+C-1) // C
d_multiples = B // D + 1 - (A+D-1) // D
lcm = C * D // gcd(C, D)
lcm_multiples = B // lcm + 1 - (A+lcm-1) // lcm

ans = total - c_multiples - d_multiples + lcm_multiples
print(ans)

Submission status: Accepted

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

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

cdiv = b//c - (a-1)//c
ddiv = b//d - (a-1)//d

div = b//lcm -(a-1)//lcm

print(b-a+1 - cdiv - ddiv + div)

Submission status: Accepted

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

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

ret_b = b - (b // c + b // d - b // f)
ret_a = (a - 1) - ((a - 1) // c + (a - 1) // d - (a - 1) // f)
ans = ret_b - ret_a
print(ans)

Submission status: Accepted

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

a, b, c, d = map(int, input().split())
m = lcm(c, d)
if a % c == 0:
    x = b // c - a // c + 1
else:
    x = b // c - a // c
if a % d == 0:
    y = b // d - a // d + 1
else:
    y = b // d - a // d
if a % m == 0:
    z = b // m - a // m + 1
else:
    z = b // m - a // m
print(b - a - x - y + z + 1)

Submission status: Accepted

Solution code:
def count(a,b,k):
    l = a + (k - (a % k)) if a % k != 0 else a
    r = b - (b % k)
    if l > r:
        return 0
    return (r-l)//k+1
def gcd(n,m):
    n,m = max(n,m),min(n,m)
    r = n % m
    while r > 0:
        n,m = m,r
        r = n % m
    return m
def lcm(n,m):
    return n*m//gcd(n,m)
a,b,c,d = map(int,input().split())
print((b-a+1)-count(a,b,c)-count(a,b,d)+count(a,b,lcm(c,d)))

Submission status: Accepted

Solution code:
A ,B ,C ,D = (map(int , input().split()))
from fractions import gcd
def lcm(x,y):
    return (x*y) // gcd(x,y)
koubaisuu = lcm(C,D)
e = B//C
f = B//D
g = B//(koubaisuu)
h = B-((e+f)-g)
AA = A - 1
ee = AA//C
ff = AA//D
gg = AA//(koubaisuu)
hh = AA-((ee+ff)-gg)
print(h-hh)

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)
s=(A-1)//C
t=(A-1)//D
u=(A-1)//lcm(C,D)
v=s+t-u
w=A-1-v
S=B//C
T=B//D
U=B//lcm(C,D)
V=S+T-U
W=B-V
print(W-w)

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

Submission status: Accepted

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

c1 = b//c
d1 = b//d
cd1 = b//(cd)

c2 = (a-1)//c
d2 = (a-1)//d
cd2 = (a-1)//cd

c3 = c1-c2
d3 = d1-d2
cd3 = cd1-cd2

print(b-a+1-c3-d3+cd3)

Submission status: Accepted

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

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

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

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())
ac, bc, ad, bd = 0, 0, 0, 0
if a % c == 0 and a % c == 0:
  ac = a // c - 1
  ad = a // d
else:
  if a % c != 0:
    ac = a // c
  else:
    ac = a // c - 1
  if a % d != 0:
    ad = a // d
  else:
    ad = a // d - 1
bc = b // c
bd = b // d
a_cd_dup = a // (lcm(c, d))
b_cd_dup = b // (lcm(c, d))
divisible_count = (bc - ac) + (bd - ad) - (b_cd_dup - a_cd_dup)
ans = (b - a + 1) - divisible_count
print(ans)

Submission status: Accepted

Solution code:
from math import floor
from fractions import gcd

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

def calc(n: int, x: int, y: int) -> int:
    return n - n//x - n//y + n//lcm(x, y)


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

a,b,c,d=mii()
c,d=min(c,d),max(c,d)

num = b-a+1

ac = (a-1)//c
bc = b//c 

ad = (a-1)//d
bd = b//d

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

print(num - (bc+bd-ac-ad)+cd)

Submission status: Accepted

Solution code:
import fractions
def gcd(a,b):
   f=fractions.gcd(a,b)
   f2=a*b//f
   return f2

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

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

a=a-1

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C, D = MAP()


if A%C == 0:
	left_c = A//C - 1
else:
	left_c = A//C
right_c = B//C

if A%D == 0:
	left_d = A//D - 1
else:
	left_d = A//D
right_d = B//D

if A%((C*D)//gcd(C, D)) == 0:
	left_w = A//((C*D)//gcd(C, D)) - 1
else:
	left_w = A//((C*D)//gcd(C, D))
right_w = B//((C*D)//gcd(C, D))

print((B - A + 1) - (right_c - left_c) - (right_d - left_d) + (right_w - left_w))

Submission status: Accepted

Solution code:
import fractions
def gcd(a,b):
   f=fractions.gcd(a,b)
   f2=a*b//f
   return f2

a,b,c,d=map(int, input().split())
bc=b//c
bd=b//d
bcd=b//gcd(c,d)

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

a -= 1

ans = b -b//c - b//d + b//e
ans = ans - (a -a//c -a//d + a//e)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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-B//C-B//D+B//E-A+A//C+A//D-A//E)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B,C,D=map(int,input().split())
def f(x,C,D):
    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:
from math import ceil
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)
nc = b//c-a//c
if a%c==0:
    nc += 1

nd = b//d-a//d
if a%d==0:
    nd += 1

ne = b//e-a//e
if a%e==0:
    ne += 1

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

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())
E=lcm(C,D)

tmp1 = B//C-A//C
if A%C==0:
  tmp1 +=1

tmp2 = B//D-A//D
if A%D==0:
  tmp2 +=1

tmp3 = B//E-A//E
if A%E==0:
  tmp3 +=1

print((B-A+1)-tmp1-tmp2+tmp3)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B, C, D = [int(i) for i in input().split()]
lcm = C*D//gcd(C, D)
ans = (B-B//C-B//D+B//lcm-(A-A//C-A//D+A//lcm))
if A < B and A % C and A % D:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

bc = B//C
ac = (A-1)//C
bd = B//D
ad = (A-1)//D
bcd = B//lcm(C,D)
acd = (A-1)//lcm(C,D)

print(B-A-bc+ac-bd+ad+bcd-acd+1)

Submission status: Accepted

Solution code:
def main():
  import fractions
  
  a,b,c,d=map(int,input().split())
  e=fractions.gcd(c,d)
  f=c*d//e
  x = (b//c - (a-1)//c)+ (b//d - (a-1)//d) - (b//f-(a-1)//f)
  y = (b-a+1)-x
  print(y)
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
import fractions

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

def count(x):
    if x>b:
        x_count = 0
    elif x<a:
        if a%x==0:
            tmp = 1
        else:
            tmp = 0

        x_count = (b-x)//x - (a-x)//x +tmp

    else:
        x_count = 1 + (b-x)//x

    return x_count

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

cd_count  = count(c)+count(d)-count(lcd(c,d))
answer = total-cd_count

print(answer)

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
lm=C*D//fractions.gcd(C,D)
cd=B//lm-(A-1)//lm

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

Submission status: Accepted

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

import fractions

def cnt_div(n,c,d):
    #n以下の整数で，cでもdでも割り切れない数の個数
    tmp1 = n // c
    tmp2 = n // d
    tmp3 = n // (c*d//fractions.gcd(c,d)) #最大公約数
    return n-(tmp1+tmp2-tmp3)

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