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: Time Limit Exceeded

Solution code:
a = [int(i) for i in input().split()]
x=0
for i in range(a[0],a[1]+1):
  if i % a[2] != 0 and i % a[3] != 0:
    x+=1
print(x)

Submission status: Time Limit Exceeded

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

num = 0
for i in range(B-A+1):
  N = A+i
  if (N%C)!=0 and (N%D)!=0:
    num += 1
    
print(num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#a = [int(x) for x in input().split()]
a, b, c, d = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re

def doit():
  res = 0
  for x in range(a, b + 1):
    if x % c == 0:
      continue
    if x % d == 0:
      continue
    res += 1
  return res

#print(doit([0] * 4))
#doit(s)
#print(doit())
try:
  print(doit())
except Exception as e:
  print("e", e, file=sys.stderr)

Submission status: Time Limit Exceeded

Solution code:
A,B,C,D = map(int, input().split())
ans=0
for x in range(A,B+1):
    if x%C!=0 and x%D!=0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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


for i in range(a,b+1):
    if i%c != 0 and i%d != 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

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

ans = 0

for i in range(A,B+1):
    if i % C > 0 and i % D > 0:
        ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())
ans = set()
for i in range(A,B+1):
    if i % C != 0 and i % D != 0:
        ans.add(i)
    else:
        pass

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:

A,B,C,D=(int(i) for i in input().split())
X=[]
for i in range(A,B+1):
    if(i%C==0):
        continue

    if(i%C!=0):
        if(i%D!=0):
            X.append(i)
            
print(len(X))

Submission status: Time Limit Exceeded

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

res = 0
for x in range(a, b+1):
    if (x%c)and(x%d):
        res += 1

print(res)

Submission status: Time Limit Exceeded

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

for i in range(a, b + 1):
    if i % c != 0 and i % d != 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

temp = [i for i in range(a, b+1)]

count = 0

for i in temp:
    if (i % c != 0) & (i % d != 0):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
A,B,C,D=map(int,input().split())
n=0
for i in range(B-A+1):
    if (A+i)%C != 0 and (A+i)%D != 0:
        n=n+1
print(n)

Submission status: Time Limit Exceeded

Solution code:


def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=y :
        x, y = max(x,y), min(x,y)
        x -= y
    return x
#print(gcd(4,8))

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

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

print(int(b-a+1-c_ok-d_ok+cd_ok))

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = (int(x) for x in input().split())
ans = 0
for i in range(a, b+1, 1):
    if i%c != 0 and i%d != 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for num in range(a, b+1):
    if num % c != 0 and num % d != 0:
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

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

p = B//C - (A-1)//C
q = B//D - (A-1)//D
r = B//l - (A-1)//l
s = p + q - r
print(B-A+1-s)

Submission status: Accepted

Solution code:

def main():
    import fractions

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

    d_c = b // c - (a-1) // c
    d_d = b // d - (a-1) // d

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

    print(b-a + 1 - (d_c + d_d - d_cd))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

s1=b//c - (a-1)//c
s2=b//d - (a-1)//d
s12=b//(c*d//math.gcd(c,d)) - (a-1)//(c*d//math.gcd(c,d))
#print(s1,s2,s12)
print(b-a+1-(s1+s2-s12))

Submission status: Accepted

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

Submission status: Accepted

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

def main():
  A, B, C, D = map(int, input().split())
  E = lcm(C, D)
  a_c, a_d, a_cd = (A-1) // C, (A-1) // D, (A-1) // E
  b_c, b_d, b_cd = B // C, B // D, B // E
  a, b = a_c + a_d - a_cd, b_c + b_d - b_cd
  ans = (B - A + 1) - (b - a)
  print(ans)
  
main()

Submission status: Accepted

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

def mul_count(v,w,n):
  if v % n == 0:
    s = v//n
  else:
    s = v//n + 1
  e = w // n
  if s > e:
    return 0
  else:
    return e - s + 1

def koyaku(x,y):
  big = max(x,y)
  small= min(x,y)
  amari = big % small
  if amari == 0:
    return small
  else:
    return koyaku(small,amari)

c_mul = mul_count(a,b,c)
d_mul = mul_count(a,b,d)

cd_common = koyaku(c,d)
cd_mul = c * d // cd_common
common_mul = mul_count(a,b,cd_mul)
yobun = c_mul + d_mul - common_mul
print(b - a + 1 - yobun)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd

def count(x, c, d):
  # x以下のcでもdでも割り切れない奴を数える
  lcm = c // gcd(c, d) * d
  return x - x // c - x // d + x // lcm

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

Submission status: Accepted

Solution code:
import fractions

a,b,c,d=map(int,input().split())
def cal(x,div1,div2):
    ret1=x//div1
    ret2=x//div2
    ret3=x//int(((div1*div2)/fractions.gcd(div1,div2)))
    return x-(ret1+ret2-ret3)
print(cal(b,c,d)-cal(a-1,c,d))

Submission status: Accepted

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

Submission status: Accepted

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

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

def num_multi(num, lb, ub): # [lb, ub]にnumの倍数がいくつあるのかを返す
    lR = lb // num
    lQ = lb % num

    uR = ub // num
    # uQ = ub % num

    ans = uR - lR
    if lQ == 0:
        ans += 1

    return ans

print((B-A+1) - num_multi(C, A, B) - num_multi(D, A, B) + num_multi(lcm, A, B))

Submission status: Accepted

Solution code:
import math

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

cd = (C * D) // math.gcd(C, D)

pac, qac = divmod(A, C)
pad, qad = divmod(A, D)
pacd, qacd = divmod(A, cd)

pbc, qbc = divmod(B, C)
pbd, qbd = divmod(B, D)
pbcd, qbcd = divmod(B, cd)

pac = pac - 1 if qac == 0 else pac
pad = pad - 1 if qad != 0 else pad
pacd = pacd - 1 if qacd != 0 else pacd

ans = (pbc + pbd - pbcd) - (pac + pad - pacd)
print(B - A - ans + 1)

Submission status: Accepted

Solution code:
import math

A,B,C,D = map(int,input().split())
divAC,modAC = divmod(A,C)
divBC,modBC = divmod(B,C)
ans = 0
if modAC == 0:
    ans += divBC - divAC + 1
else:
    ans += divBC - divAC

divAD,modAD = divmod(A,D)
divBD,modBD = divmod(B,D)
if modAD == 0:
    ans += divBD - divAD + 1
else:
    ans += divBD - divAD
divACD,modACD = divmod(A,int(C * D / math.gcd(C, D)))
divBCD,modBCD = divmod(B,int(C * D / math.gcd(C, D)))
if modACD == 0:
    ans -= divBCD - divACD + 1
else:
    ans -= divBCD - divACD

print(B-A+1-ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    A, B, C, D = LI()

    # X以下の自然数でCでもDでも割り切れないものの個数
    def f(X):
        ret = X - X // C - X // D + X // (C * D // math.gcd(C, D))
        return ret

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

# CとDの最大公約数をユークリッドの互除法より求め、最小公倍数を導出
while c!=0 and d!=0:
    if c > d:
        c %= d
    else:
        d %= c

gcd = max(c,d)
# B以下の整数からCの倍数とDの倍数の数を引いた数を求める
# A-1に関しても同様の処理を行い、その差が答えとなる
A_prime = A-1
print((B-(B//C+B//D)+(B//(C*D//gcd)))-
     (A_prime-(A_prime//C+A_prime//D)+(A_prime//(C*D//gcd))))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

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

c_div=(b//c)-((a-1)//c)
d_div=(b//d)-((a-1)//d)
cd_div=(b//lcm(c,d))-((a-1)//lcm(c,d))

ans=(b-a+1)-((c_div)+(d_div)-(cd_div))
print(ans)

Submission status: Accepted

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

ans_b=b-(b//c)-(b//d)+(b//(lcm(c,d)))
ans_a=a-(a//c)-(a//d)+(a//(lcm(c,d)))
ans=ans_b-ans_a

if a%c!=0 and a%d!=0:
    ans+=1
print(ans)

Submission status: Accepted

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

abc131c_anti_division()

Submission status: Accepted

Solution code:
import math

def solve(a,c,d):
    x=a+1
    x-=a//c+1
    x-=a//d+1
    x+=a//(c*d//math.gcd(c,d))+1
    return x

A,B,C,D=map(int,input().split())
print(solve(B,C,D)-solve(A-1,C,D))

Submission status: Accepted

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

Submission status: Accepted

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

# for文は間に合わないので、包除原理を使え！

# CでもDでも割り切れない =
# 全体(a) - Cで割り切れる(b) + Dで割り切れる(c)
# + CでもDでも割り切れる(d)

# Cで割り切れる個数 =
# B以下の数でCで割り切れる個数 - (A−1)以下の数でCで割り切れる個数

lcm = C*D // math.gcd(C, D)
a = B - A + 1
b = B // C - (A-1) // C
c = B // D - (A-1) // D
d = B // lcm - (A-1) // lcm
 
print(a-b-c+d)

Submission status: Accepted

Solution code:
import math
A, B, C, D = map(int, input().split())
 
# CでもDでも割り切れない = 全体(a) - Cで割り切れる(b) + Dで割り切れる(c) + CでもDでも割り切れる(d)
lcm = C*D // math.gcd(C, D)
a = B - A + 1
b = B // C - (A-1) // C
c = B // D - (A-1) // D
d = B // lcm - (A-1) // lcm

print(a-b-c+d)

Submission status: Accepted

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

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())
def div(x):
    num=x
    num-=x//C
    num-=x//D
    num+=x//lcm(C,D)
    return num
print(div(B)-div(A-1))

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 131
# C - Anti-Division
import math

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

A,B,C,D=map(int,input().split())
bc=B//C
ac=(A-1)//C
cnum=bc-ac

bd=B//D
ad=(A-1)//D
dnum=bd-ad


lcmcd=lcm(C,D)
blcmcd=B//lcmcd
alcmcd=(A-1)//lcmcd
lcmcdnum=blcmcd-alcmcd


print(B-A-cnum-dnum+lcmcdnum+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

m = b//c + (-a//c)
n = b//d + (-a//d)
g = c * d // math.gcd(c, d)
p = b//g + (-a//g) 
print(b-a+1-(m+1+n+1-(p+1)))

Submission status: Accepted

Solution code:
import math

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

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

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

Submission status: Accepted

Solution code:
import math

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

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

l=lcm(C,D)

temp=l-(l//C+l//D-1)

a=(A-1)%l
b=B%l

aa=(A-1)//l
bb=B//l

tempA=a-(a//C+a//D-1)
tempB=b-(b//C+b//D-1)
            

ans=temp*bb+tempB-(temp*aa+tempA)


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 11 12:42:46 2020

@author: liang
"""

import math

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

B_ans = B - B//C - B//D + B//E
#print(B_ans)
A -= 1
A_ans = A - A//C - A//D + A//E
#print(A_ans)
ans = B_ans - A_ans
print(ans)

Submission status: Accepted

Solution code:
import math

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

n=b-a+1

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

cc=b//c-(a-1)//c
dc=b//d-(a-1)//d
xc=b//x-(a-1)//x

print(n-cc-dc+xc)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math as m
A,B,C,D=map(int,input().split())
A-=1
g=C*D//m.gcd(C,D)
x=B//C-A//C
y=B//D-A//D
z=B//g-A//g
print(B-A-x-y+z)

Submission status: Accepted

Solution code:
import math
a,b,c,d = map(int,input().split())
e = c*d//math.gcd(c,d)
wa = 0
c_seki = b//c-(a-1)//c
d_seki = b//d-(a-1)//d
e_seki = b//e-(a-1)//e
wa = c_seki+d_seki-e_seki
print(b-a+1-wa)

Submission status: Accepted

Solution code:
a,b,c,d = map(int,input().split())
from math import gcd
e  =c*d//gcd(c,d)
xa = a//c if a%c else a//c - 1
xb = b//c
ya = a//d if a%d else a//d - 1
yb = b//d
za = a//e if a%e else a//e - 1
zb = b//e
x = xb-xa
y  = yb-ya
z = zb-za
print(b-a+1-x-y+z)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def warikirenai(n, c, d):
    num =  n - n // c
    num += n - n // d
    num -= n - n // lcm(c, d)
    return num

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

def warikirenai(n, warukazu):
    return n - n // warukazu
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

    ansA = 0
    ansA += warikirenai(A - 1, C)
    ansA += warikirenai(A - 1, D)
    ansA -= warikirenai(A - 1, lcm(C, D))

    ansB = 0
    ansB += warikirenai(B, C)
    ansB += warikirenai(B, D)
    ansB -= warikirenai(B, lcm(C, D))

    print(ansB - ansA)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)

A,B,C,D = mint()

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

print(f(1)-f(C)-f(D)+f(lcm(C,D)))

Submission status: Accepted

Solution code:
import math
a,b,c,d=map(int,input().split())
e=c*d//math.gcd(c,d)
if a%c==0:
  p=b//c-a//c+1
else:
  p=b//c-a//c
if a%d==0:
  q=b//d-a//d+1
else:
  q=b//d-a//d
if a%e==0:
  r=b//e-a//e+1
else:
  r=b//e-a//e
print(b-a+1-(p+q-r))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

a, b, c, d = map(int, input().split())
l = c * d // math.gcd(c, d)
all = b - a + 1
can_c = b // c - (a - 1) // c
can_d = b // d - (a - 1) // d
can_cd = b // l - (a - 1) // l
ans = all - can_c - can_d + can_cd
print(ans)

Submission status: Accepted

Solution code:
import sys

def gcd(a, b):
    """
    最大公約数を求める
    """
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """
    最小公倍数を求める
    """
    return a*b//(gcd(a, b))


input = sys.stdin.readline

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

div_ac = (a-1) // c
div_bc = b // c


div_ad = (a-1) // d
div_bd = b // d

lcm_cd = lcm(c,d)

div_acd = (a-1) // lcm_cd
div_bcd = b // lcm_cd

a_1_result =  div_ac + div_ad - div_acd
b_result = div_bc + div_bd - div_bcd

print((b+1 - a) - (b_result - a_1_result))

Submission status: Accepted

Solution code:
def main():
    from math import gcd
    a, b, c, d = (int(i) for i in input().split())
    L = c*d//gcd(c, d)
    ans = b - (b//c + b//d - b//L)
    ans -= (a-1) - ((a-1)//c + (a-1)//d - (a-1)//L)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 解説動画みた： https://www.youtube.com/watch?v=XI8exXVxZ-Q
# 最小公倍数
# ユーグリッドの互除法

import math

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

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

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

Submission status: Accepted

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

def main():
    A,B,C,D = map(int,input().split())
    #Cで割り切れる数の探索
    tmpC = (A-1)//C
    tmpC2 = (B)//C
    numC = tmpC2 - tmpC
    #Dで割り切れる数の探索
    tmpD = (A-1)//D
    tmpD2 = (B)//D
    numD = tmpD2 - tmpD
    #CでもDで割り切れるもの
    if C == D:
        ans = B-A+1-numC
    else:
        tmpCD = (A-1)//lcm(C,D)
        tmpCD2 = (B)//lcm(C,D)
        numCD = tmpCD2 - tmpCD
        ans = B-A+1-numC-numD+numCD
    return ans
print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


A,B,C,D = MI()

from math import gcd


def f(n):
    return n-n//C-n//D+n//((C*D)//gcd(C,D))


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

Submission status: Accepted

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


def calc(x):
    global c, d
    l = c // math.gcd(c, d) * d
    return x - x // c - x // d + x // l


print(calc(b) - calc(a - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

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

bc = B // C
bd = B // D
bg = B // lcm
ac = (A-1) // C
ad = (A-1) // D
ag = (A-1) // lcm

print(B - A + 1 - (bc - ac) - (bd - ad) + (bg - ag))

Submission status: Accepted

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

from math import gcd

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

b_div_c = b//c
a_div_c = (a-1)//c

b_div_d =b//d
a_div_d = (a-1)//d

b_div_cd = b//lcm
a_div_cd = (a-1)//lcm



ans1 = b_div_c - a_div_c
ans2 = b_div_d - a_div_d
ans3 = b_div_cd - a_div_cd

ans = b -(a-1) - ans1 - ans2 + ans3
print(ans)

Submission status: Accepted

Solution code:
import math
def lcm(a):
    LCM = a[0]
    for i in range(1, len(a)):
        LCM = LCM * a[i] // math.gcd(LCM, a[i])
    return LCM

def f(k):
    return b//k - (a-1)//k

a, b, c, d = map(int, input().split())
ALL = b - a + 1
ans = ALL - (f(c) + f(d) - f(lcm([c,d])))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

nc=b//c-(a-1)//c
nd=b//d-(a-1)//d
cd=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(x,y):
    while y>0:
        x,y = y,x%y
    return x
A,B,C,D = map(int,input().split())
a = gcd(C,D)
E = (C//a)*D
n1 = B//C
n2 = B//D
n3 = B//E
n = B-(n1+n2-n3)
m1 = (A-1)//C
m2 = (A-1)//D
m3 = (A-1)//E
m = A-1-(m1+m2-m3)
print(n-m)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


A,B,C,D = MI()


from math import gcd


def f(n):
    return n-n//C-n//D+n//((C*D)//gcd(C,D))


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

Submission status: Accepted

Solution code:
from math import gcd


def f(x):
    return x - (x // C + x // D - x // lcm)


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

Submission status: Accepted

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

A, B, C, D = [int(x) for x in input().split()]
if C > D:
    E = C * D // gcd(C, D)
else:
    E = C * D // gcd(D, C)

divC = B // C - (A - 1) // C
divD = B // D - (A - 1) // D
divE = B // E - (A - 1) // E
div = divC + divD - divE
ans = B - A + 1 - div

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
a-=1
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)
aa= b//c-a//c 
bb= b//d-a//d 
cc= b//lcm(c,d)- a//lcm(c,d)
print(b-a-(aa+bb-cc))

Submission status: Accepted

Solution code:
import math
A,B,C,D = map(int,input().split())
BIkaCbaisuC = B//C
AIkaCbaisuC = (A-1)//C
ABkanCbaisuC = BIkaCbaisuC - AIkaCbaisuC

BIkaDbaisuC = B//D
AIkaDbaisuC = (A-1)//D
ABkanDbaisuC = BIkaDbaisuC - AIkaDbaisuC

cd = math.floor(C*D/math.gcd(C,D))
BIkacdbaisuC = B//cd
AIkacdbaisuC = (A-1)//cd
ABkancdbaisuC = BIkacdbaisuC - AIkacdbaisuC

print(B-A+1-ABkanCbaisuC-ABkanDbaisuC+ABkancdbaisuC)

Submission status: Accepted

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

Submission status: Accepted

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

LCD = C*D//math.gcd(C,D)

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

print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix
# CreatedDate:  2020-09-03 20:30:23 +0900
# LastModified: 2020-09-03 21:14:03 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


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


def main():
    a, b, c, d = map(int, input().split())
    if (a/c).is_integer():
        c_cnt = b//c - a//c + 1
#        print(b//c, a//c)
    else:
        c_cnt = b//c - a//c
#        print(b//c, a//c)
    if (a/d).is_integer():
        d_cnt = b//d - a//d + 1
#        print(b//d, a//d)
    else:
        d_cnt = b//d - a//d
#        print(b//d, a//d)

    lcm = c * d // gcd(max(c, d), min(c, d))
    if (a/lcm).is_integer():
        lcm_cnt = b//lcm - a//lcm + 1
    else:
        lcm_cnt = b//lcm - a//lcm
#    print(c_cnt, d_cnt, lcm_cnt)
    print(b-a+1-c_cnt-d_cnt+lcm_cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if a%c==0:
    n=b//c-a//c+1
else:
    n=b//c-a//c
if a%d==0:
    m=b//d-a//d+1
else:
    m=b//d-a//d
e=(c*d)//math.gcd(c,d)
if a%e==0:
    k=b//e-a//e+1
else:
    k=b//e-a//e
k=n+m-k
print(b-a-k+1)

Submission status: Accepted

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

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

lcm = lcm(C,D)

u_b_ans = (B//C + B//D) - B//lcm
u_a_ans = ((A-1)//C + (A-1)//D) - (A-1)//lcm

print(B-A+1 - u_b_ans + u_a_ans)

Submission status: Accepted

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

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

lcm = lcm(C,D)

u_b_ans = (B//C + B//D) - B//lcm
u_a_ans = ((A-1)//C + (A-1)//D) - (A-1)//lcm

print(B-A+1 - u_b_ans + u_a_ans)

Submission status: Accepted

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

cyaku=b//c
dyaku=b//d


cds=b//((c*d)//(math.gcd(c,d)))

x=b-(cyaku+dyaku-cds)

cyaku2=(a-1)//c
dyaku2=(a-1)//d

cds2=(a-1)//((c*d)//(math.gcd(c,d)))

y=(a-1)-(cyaku2+dyaku2-cds2)

print(x-y)

Submission status: Accepted

Solution code:
import math


def cnt(a: int, k: int):
    return a // k


def num(a, c, d):
    m_a_c = cnt(a, c)
    m_a_d = cnt(a, d)
    m_a_cd = cnt(a, c * d // math.gcd(c, d))
    return a - m_a_c - m_a_d + m_a_cd


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

Submission status: Accepted

Solution code:
#35 C - Anti-Division　
import math
A,B,C,D = map(int,input().split())

# C と D の最小公倍数の個数
lcm = C*D//math.gcd(C,D)
cnt_lcm = B//lcm - (A-1)//lcm

# C の倍数の個数
cnt_C = B//C - (A-1)//C 

# D の倍数の個数
cnt_D = B//D - (A-1)//D

# (範囲内の整数) - (C の倍数 + D の倍数 - C,D の公倍数)
ans = (B - A + 1) - (cnt_C + cnt_D - cnt_lcm)

# 範囲が 1 しかないとき
if A == B:
    # C でも D でも割り切れるとき
    if A%C == 0 and A%D == 0:
        print(0)
    else:
        print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math
A,B,C,D=map(int,input().split())
res = B-A+1
mid = 0
cd = C * D // math.gcd(C, D)
miniNumC = A//C
if A%C==0:
  miniNumC += -1
miniNumD = A//D
if A%D==0:
  miniNumD += -1
maxNumC = B//C
maxNumD = B//D
miniNumCD = A//cd
maxNumCD = B//cd
if A%cd==0:
  miniNumCD += -1
mid += maxNumC -miniNumC + maxNumD -miniNumD -maxNumCD +miniNumCD 
print(res-mid)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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