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:
#!/usr/bin/env python3
import fractions


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

    num_C = B // C - (A - 1) // C
    num_D = B // D - (A - 1) // D
    lcm = C * D // fractions.gcd(C, D)
    num_CD = B // lcm - (A - 1) // lcm

    ans = (B - A + 1) - num_C - num_D + num_CD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
def gcd(a,b):
    r = a%b;
    while r > 0:
        a = b
        b = r
        r = a%b
    return b
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    a,b,c,d = map(int,read().split())
    acnum = (a-1)//c
    bcnum = (b)//c
    adnum = (a-1)//d
    bdnum = (b)//d
    acdnum = (a-1)//(lcm(c,d))
    bcdnum = (b)//(lcm(c,d))

    print((b-a+1)-(bcnum-acnum)-(bdnum-adnum) + (bcdnum-acdnum))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
from fractions import gcd
a -= 1
nya = c//gcd(c,d) * d # 最小公倍数
# オイラー関数
ca = a//c
da = a//d
#print(ca,da)
cda = ca + da - a//nya
ans_a = a - cda
cb = b//c
db = b//d
#print("cddb",cb,db)
cdb = cb + db - b//nya
ans_b = b - cdb
print(ans_b - ans_a)
#print(ans_a,ans_b)
#print(nya)
#ans = ans_b - ans_a
#print(ans)

Submission status: Accepted

Solution code:
A, B, C, D = map(int, input().split())
import fractions
g = fractions.gcd(C, D)
ac = (A-1)//C
bc = B//C
c = bc-ac
ad = (A-1)//D
bd = B//D
d = bd-ad
cdg = (C*D)//g
acd = (A-1)//cdg
bcd = B//cdg
cd = bcd-acd
ans = B-A+1-c-d+cd
print(ans)

Submission status: Accepted

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

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

A, B, C, D = map(int, input().split())
cnt = B - A + 1
all_range = B // C + B // D - B // lcm(C , D)
sub_end = A - 1
sub_range = sub_end // C + sub_end // D - sub_end // lcm(C , D)
print(cnt - (all_range - sub_range))

Submission status: Accepted

Solution code:
import sys
from math import pi

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

def solve():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    cDiv = (B // C) - ((A - 1) // C)
    dDiv = (B // D) - ((A - 1) // D)
    cd = C * D // gcd(C, D)
    cdDiv = (B // cd) - ((A - 1) // cd)
    print((B - A + 1) - (cDiv + dDiv - cdDiv))
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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())
E = (C//gcd(C,D))*D
c1 = B//C
d1 = B//D
e1 = B//E
y = B-(c1+d1-e1)
c2 = (A-1)//C
d2 = (A-1)//D
e2 = (A-1)//E
x = (A-1)-(c2+d2-e2)
print(y-x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def f(x):
    return B//x-(A-1)//x

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())
print(B-A+1-f(C)-f(D)+f(lcm(C, D)))

Submission status: Accepted

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

A = b - (b//c + b//d -  b//e)
B = a - (a//c + a//d - a//e)
print(A-B)

Submission status: Accepted

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

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)

def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

l = lcm_base(c, d)

i = b//c-(a-1)//c
j = b//d-(a-1)//d
k = b//l-(a-1)//l
#print(i, j, k)
ans = b-a+1-(i+j-k)
print(ans)

Submission status: Accepted

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


def LCM(x, y):
    return x // GCD(x, y) * y


def F(X, C, D):
    res = X // C + X // D
    res -= X // LCM(C, D)
    return res


if __name__ == "__main__":
    A, B, C, D = map(int, input().split())
    can_div = F(B, C, D) - F(A - 1, C, D)
    print(B - A + 1 - can_div)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from fractions import gcd
def resolve():
    a, b, c, d = map(int, input().split())
    L = c // gcd(c, d) * d
    a -= 1
    S = b - b // c - b // d + b // L
    T = a - a // c - a // d + a // L
    print(S - T)
resolve()

Submission status: Accepted

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

ans = B-A+1

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

ans -= B//C

ans -= B//D

ans += B//LCM

ans += (A-1)//C

ans += (A-1)//D

ans -= (A-1)//LCM
print(ans)

Submission status: Accepted

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

nums = b-a+1
t1 = b//c - (a-1)//c
t2 = b//d - (a-1)//d

lcm = (c*d)//gcd(c,d)
t3 = b//lcm - (a-1)//lcm
print(nums-t1-t2+t3)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
## C - Anti-Division
from fractions import gcd
A, B, C, D = map(int, input().split())
s = B-A+1
t = B//C - (A-1)//C
u = B//D - (A-1)//D
v = B//( (C*D)//gcd(C,D) ) - (A-1)//( (C*D)//gcd(C,D) )
print(s - t - u + v)

Submission status: Accepted

Solution code:
from fractions import gcd

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

if a%c == 0:
    c_number = b // c - a // c + 1
else:
    c_number = b // c - a // c
if a%d == 0:
    d_number = b // d - a // d + 1
else:
    d_number = b // d - a // d
if a%(c*d // gcd(c,d)) == 0:
    cd_number = b // (c*d // gcd(c,d)) - a // (c*d // gcd(c,d)) + 1
else:
    cd_number = b // (c*d // gcd(c,d)) - a // (c*d // gcd(c,d))
print(int((b-a+1) - (c_number + d_number - cd_number)))

Submission status: Accepted

Solution code:
from fractions 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:
from fractions import gcd
a,b,c,d=map(int,input().split())
count=b-a+1
temp1=b//c-(a-1)//c
temp2=b//d-(a-1)//d
temp3=b//int((c*d)/gcd(c,d))-(a-1)//int((c*d)/gcd(c,d))
print(int(count-temp1-temp2+temp3))

Submission status: Accepted

Solution code:
import fractions
lcm = lambda a, b: a * b // fractions.gcd(a, b)
A, B, C, D = map(int, input().split(' '))
div_A = A - 1 - (A - 1) // C - (A - 1) // D + (A - 1) // lcm(C, D)
div_B = B - B // C - B // D + B // lcm(C, D)
print(div_B - div_A)

Submission status: Accepted

Solution code:
import fractions

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

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

Submission status: Accepted

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

import fractions
lcmcd = c * d // fractions.gcd(c,d)
bc = b // c
ac = a // c
bd = b // d
ad = a // d
blcmcd = b // lcmcd
alcmcd = a // lcmcd

if a % c != 0:
    ac += 1
if a % d != 0:
    ad += 1
if a % lcmcd != 0:
    alcmcd += 1

print((b - a + 1) - ((bc - ac + 1) + (bd - ad + 1) - (blcmcd -alcmcd + 1)))

Submission status: Accepted

Solution code:
import fractions

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


i = (a-1) // c #aのcの約数の数
j = b // c #bのcの約数の数
k = (a-1) // d #aのdの約数の数
l = b // d #bのdの約数の数
m = (a-1) // (e) #aのc*dの約数の数
n = b // (e) #bのc*dの約数の数

x = (j-i) + (l-k) - (n-m)
y = b - a + 1
print(y-x)

Submission status: Accepted

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

Submission status: Accepted

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

from fractions import gcd

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


def calc(min_, max_, div_num):
    if (min_ % div_num) != 0:
        min_ = min_ - (min_ % div_num)+div_num

    if min_ > max_:
        return 0
    return (max_-min_)//div_num+1


# print(calc(a, b, c))
# print(calc(a, b, d))
# print(calc(a, b, c*d//gcd(c, d)))
print((b-a+1)-(calc(a, b, c)+calc(a, b, d)-calc(a, b, c*d//gcd(c, d))))

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil, floor, sqrt
from copy import deepcopy
from fractions import gcd

def main():
    a,b,c,d = map(int, input().split())
    a -= 1
    num = int(c*d / gcd(c,d))
    num_a = a - int(a // c + a // d - a // num)
    num_b = b - int(b // c + b // d - b // num)
    print(num_b - num_a)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

lcm=c*d // fractions.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 sys
import math

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

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

  
a,b,c,d = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
e = b - a + 1
if c == d:
  fgh = (b // c) - ((a - 1) // c)
  n = e - fgh
  print(n) 
else:
  f = (b // c) - ((a - 1) // c)
  g = (b // d) - ((a - 1) // d)
  cd = lcm(c, d) 
  h = (b // cd) - ((a - 1) // cd)
  n = e - f - g + h
  print(n)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import fractions

a,b,c,d = mi()

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

# cの倍数の個数
ac = (a-1)//c
bc = b//c
nc = bc-ac

# dの倍数の個数
ad = (a-1)//d
bd = b//d
nd = bd-ad

# cdのgcdの倍数の個数
ag = (a-1)//g
bg = b//g
ng = bg-ag

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

# print(g,nc,nd,ng)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

A, B, C, D = getNM()

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

def split(n, m1, m2):
    opt1 = n // m1
    opt2 = n // m2
    opt3 = n // lcm_base(m1, m2)
    return n  - (opt1 + opt2 - opt3)
print(split(B, C, D) - split(A - 1, C, D))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import fractions
    a, b, c, d = map(int, input().split())
    e = c * d // fractions.gcd(c, d)
    def main(x):
        ckosu=x//c
        dkosu=x//d
        ekosu=x//e
        return ckosu+dkosu-ekosu
    print(b-a+1-((main(b)-main(a-1))))
resolve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import fractions
    a,b,c,d=map(int, input().split())
    e=c*d//fractions.gcd(c,d)
    ckosu=b//c-(a-1)//c
    dkosu=b//d-(a-1)//d
    ekosu=b//e-(a-1)//e
    print(b-a+1-(ckosu+dkosu-ekosu))
resolve()

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

Solution code:
import math

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

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

gcd_ = int(gcd(c,d))

cc = (c//gcd_ * d)


mm1 = b//c
mm2 = b//d
mmc = b//cc
A1 = b - (mm2 + mm1 - mmc)
# print(A1, b, mm2, mm1, mmc)

a-=1
mm1 = a//c
mm2 = a//d
mmc = a//cc
A2 = a - (mm2 + mm1 - mmc)
# print(A2, a, mm2, mm1, mmc)


print(A1 - A2)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

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

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

A,B,C,D = IL()

L = lcm(C,D)


def papa(x,y):
  N = lcm(x,y)
  return N-N//x-N//y+1
P = papa(C,D)
def coco(x,l):
  r = x%l
  return x//l * P + r-r//C-r//D

print(coco(B,L)-coco(A-1,L))

Submission status: Accepted

Solution code:
def baisu(n, a):
  return n // a

def baisu2(n, m, a):
  return baisu(m, a)-baisu(n-1, a)

import fractions

def lcm(k):
    ans = k[0]
    for i in range(1, len(k)):
        ans = ans * k[i] // fractions.gcd(ans, k[i])
    return ans

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

cbaisu = baisu2(a, b, c)
dbaisu = baisu2(a, b, d)
cdbaisu = baisu2(a, b, lcm([c, d]))

print(b-a+1-cbaisu-dbaisu+cdbaisu)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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)

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

a, b, c, d = map(int, input().split())
c_m = b // c - (a - 1) // c
d_m = b // d - (a - 1) // d
cd_m = b // (lmc(c, d)) - (a - 1) // (lmc(c, d))
ans = b - a + 1 - (c_m + d_m - cd_m)
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

cntC = B // C - A // C + int(A % C == 0)
cntD = B // D - A // D + int(A % D == 0)

lcm = C * D // fractions.gcd(C, D)
cntCD = B // lcm - A // lcm + int(A % lcm == 0)

print((B - A + 1) - (cntC + cntD - cntCD))

Submission status: Accepted

Solution code:
import math

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

C, D = c, d
if C < D:
  C, D = D, C
r = C % D
while r > 0:
  C = D
  D = r
  r = C % D
lcm = c * d // D

cPower = b//c - math.ceil(a/c) + 1
dPower = b//d - math.ceil(a/d) + 1
cdPower = b//lcm - math.ceil(a/lcm) + 1

print(max((b-a+1) - cPower - dPower + cdPower, 0))

Submission status: Accepted

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

def divide(n):
    return (b // n) - ((a-1) // n)

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

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

ans = b - a + 1

ans -= divide(c)

ans -= divide(d)

ans += divide(lcm(c,d))

print(ans)

Submission status: Accepted

Solution code:
import fractions
def count(n, m, l):
    c_m = n // m
    c_l = n // l
    c_ml = n // (m * l // fractions.gcd(m, l))
    return n - (c_m + c_l - c_ml)

a, b, c, d = map(int, input().split())
b_tar = count(b, c, d)
a_tar = count(a, c, d)
is_plus_a = not(bool(a % c == 0 or a % d == 0))
ans = b_tar - a_tar
if is_plus_a: ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 判定機にmathがインストールされていないため、
# gcd=最小公倍数、lcm=最少公約数(返り値整数)を実装
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    z = None
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        return z


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


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

# check
AB = B - (A - 1)

C_cnt = B // C - (A - 1) // C
D_cnt = B // D - (A - 1) // D

lcm_CD = lcm(C, D)
lcm_cnt = B // lcm_CD - (A - 1) // lcm_CD

ans = AB - C_cnt - D_cnt + lcm_cnt

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

Submission status: Accepted

Solution code:
import fractions
li = list(map(int,input().split()))
countC = li[1] // li[2] - (li[0]-1) // li[2]

countD = li[1] // li[3] - (li[0]-1) // li[3]

lcm = (li[2] * li[3]) // fractions.gcd(li[2], li[3])

countCD = li[1] // lcm - (li[0]-1) // lcm

re = (li[1] - li[0] + 1) - (countC +countD - countCD)

print(re)

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


def count_target(n):
    c_multiples = n // C
    d_multiples = n // D
    cd_multiples = n // lcm_cd
    return n - c_multiples - d_multiples + cd_multiples


count2a = count_target(A - 1)
count2b = count_target(B)

print(count2b - count2a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
a, b, c, d  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

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)

nlcmc = b // c
nlcmd = b // d
nlcmcd = b // lcm(c, d)
nb = b - (nlcmc + nlcmd - nlcmcd)

a -= 1
nlcmc = a // c
nlcmd = a // d
nlcmcd = a // lcm(c, d)
na = a - (nlcmc + nlcmd - nlcmcd)

print(nb - na)

Submission status: Accepted

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

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

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

N = B - A + 1

g = lcm(C,D)
C_ = B//C - (A-1)//C
D_ = B//D - (A-1)//D
CD_ = B//g - (A-1)//g
ans = N - C_ - D_ + CD_
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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


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


def sj(base, i1, i2):
    cz = base // i1
    dz = base // i2
    cd = base // lcm(i1, i2)
    return base - (cz + dz - cd)


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

Submission status: Accepted

Solution code:
from fractions import gcd


def list_lcm(A):
    """N個の最小公倍数
    Args:
        A (list[int])

    Returns:
        int: 最小公倍数

    Examples:
        >>> list_lcm([12, 34, 54, 65])
        119340
    """
    ans = A[0]
    for i in range(1, len(A)):
        ans = ans * A[i] // gcd(ans, A[i])
    return ans


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

    lcm_C_D = list_lcm([C, D])
    ans_B = B - B // C - B // D + B // lcm_C_D
    ans_A = A - A // C - A // D + A // lcm_C_D

    print(ans_B - ans_A)


resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))
import fractions

a,b,c,d=input_list()

l_c=(a+c-1)//c
h_c=b//c
c_num=h_c-l_c+1

l_d=(a+d-1)//d
h_d=b//d
d_num=h_d-l_d+1


g=c*d//fractions.gcd(c,d)
l_g=(a+g-1)//g
h_g=b//g
g_num=h_g-l_g+1

ans=b-a+1-c_num-d_num+g_num
print(ans)

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

# lcm = lambda x, y: (x * y) / math.gcd(x, y)
lcm = lambda x, y: x * y // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, C, D = il()
    E = B - A + 1
    cnt = 0

    cnt += B // C
    cnt += B // D
    cnt -= (A-1) // C
    cnt -= (A-1) // D

    cnt -= B // lcm(C, D)
    cnt += (A-1) // lcm(C, D)
    print(E - cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
nums = input()
intNums = []

def saidaiKouYaku(a, b):
    if a < b:
        tmp = a
        a = b
        b = tmp

    r = a % b
    while(r != 0):
        a = b
        b = r
        r = a % b
    return b


for n in nums.split():
    intNums.append(int(n))
    
if len(intNums) == 4 and intNums[0] <= intNums[1] \
    and (intNums[0] >= 1 and intNums[0] <= 10**18) \
    and (intNums[1] >= 1 and intNums[1] <= 10**18) \
    and (intNums[2] >= 1 and intNums[2] <= 10**9) \
    and (intNums[3] >= 1 and intNums[3] <= 10**9):

    # 逆にどちらかで割り切れる数を調べる
    # C,D の最大公約数
    saidaiKouYaku = saidaiKouYaku(intNums[2], intNums[3])
    
    # C,Dの最小公倍数は　積 / 最大公約数
    saisyoKoubai = (intNums[2] * intNums[3]) // saidaiKouYaku
#     print('saidaiKouYaku = ',saidaiKouYaku)
#     print('saisyoKoubai = ',saisyoKoubai)
    c1 = intNums[1] // intNums[2] - (intNums[0]-1) // intNums[2]
    c2 = intNums[1] // intNums[3] - (intNums[0]-1) // intNums[3]
    c3 = intNums[1] // saisyoKoubai - (intNums[0]-1) // saisyoKoubai
#     print(c1)
#     print(c2)
#     print(c3)
    c4 = c1 + c2 - c3
    result = (intNums[1] - (intNums[0]-1)) - c4
    print(result)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy

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

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

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
import fractions
s1 = b//c
s2 = (a-1)//c
p1 = b//d
p2 = (a-1)//d
e = c*d//fractions.gcd(c,d)
q1 = b//e
q2 = (a-1)//e
print(b-a+1-(s1+p1-s2-p2-q1+q2))

Submission status: Accepted

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

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



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

if A % C ==0:
    c = (B//C) - (A//C) +1
else:
    c = (B//C) - (A//C)

if A % D ==0:
    d = (B//D) - (A//D) +1
else:
    d = (B//D) - (A//D)

E = lcm(C,D)

if A % E ==0:
    e = (B//E) - (A//E) +1
else:
    e = (B//E) - (A//E)

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

Submission status: Accepted

Solution code:
from fractions import gcd
def kosuu(n):
    global a,b
    return b//n-(a-1)//n
a,b,c,d = map(int,input().split())
e = int(c*d/gcd(c,d))
print(b-a+1-kosuu(c)-kosuu(d)+kosuu(e))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
e = int(c*d/gcd(c,d))
n1 = b//c-a//c if a%c != 0 else b//c-a//c+1
n2 = b//d-a//d if a%d != 0 else b//d-a//d+1
n3 = b//e-a//e if a%e != 0 else b//e-a//e+1
print(b-a+1-n1-n2+n3)

Submission status: Accepted

Solution code:
import fractions
a, b, c, d = list(map(int, input().split()))
ans = []
for n in [a - 1, b]:
    mc = n // c
    md = n // d
    cd = c * d // fractions.gcd(c, d)
    mcd = n // cd
    ans.append(n - mc - md + mcd)
print(int(ans[1] - ans[0]))

Submission status: Accepted

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


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


def count(X, C, D):
    ret = X - (X//C + X//D - X//lcm(C, D))
    return ret


def main():
    A, B, C, D = map(int, input().split())
    ans = count(B, C, D) - count(A-1, C, D)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Ans = []

for i in [B,A-1]:
  N = i
  E = (C * D) // gcd(C,D)
  modC = N//C
  modD = N//D
  modE = N//E
  Ans += [N - modC - modD + modE]
  
print(Ans[0]-Ans[1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri May 15 00:52:33 2020

@author: Kanaru Sato
"""

import fractions

def divnum(x,y,n):
    if x%n == 0:
        return y//n - x//n + 1
    else:
        return y//n - x//n

a,b,c,d = list(map(int,input().split()))
cd = (c*d)//fractions.gcd(c,d)
ans = divnum(a,b,c) + divnum(a,b,d) - divnum(a,b,cd)
print(b-a+1-ans)

Submission status: Accepted

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


def gcd(p, q):
	if p % q == 0:
		return q
	else:
		return gcd(q, p % q)

def cnt(A, B, K):
    a = (A // K + (A % K != 0)) * K
    b = (B // K) * K
    if a > b:
        return 0
    else:
        return (b - a) // K + 1


lcm = c * d // gcd(c, d)
res1 = cnt(a, b, c)
res2 = cnt(a, b, d)
res3 = cnt(a, b, lcm)
print(b - a + 1 - res1 -res2 + res3)

Submission status: Accepted

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

"""
両方に関して割り切れるものの個数から公倍数で割り切れるものを除けばいい
"""
import fractions

C = b//c - (a-1)//c
D = b//d - (a-1)//d

# 最小公倍数を求める
CD = fractions.gcd(c, d)
lcm = (c * d) // CD

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


count = C + D - G
print(b - a + 1 - count)

Submission status: Accepted

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

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 f(e):
   return e - (e//c + e//d - e//(c*d//gcd(c,d)))

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

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
total=b-a+1
cdiv=b//c-(a-1)//c
ddiv=b//d-(a-1)//d
CDdiv=(c*d)//fractions.gcd(c,d)
cddiv=b//(CDdiv)-(a-1)//(CDdiv)
print(total-cdiv-ddiv+cddiv)

Submission status: Accepted

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