You are given two arithmetic progressions: a_1k + b_1 and a_2l + b_2. Find the number of integers x such that L ≤ x ≤ R and x = a_1k' + b_1 = a_2l' + b_2, for some integers k', l' ≥ 0.


-----Input-----

The only line contains six integers a_1, b_1, a_2, b_2, L, R (0 < a_1, a_2 ≤ 2·10^9,  - 2·10^9 ≤ b_1, b_2, L, R ≤ 2·10^9, L ≤ R).


-----Output-----

Print the desired number of integers x.


-----Examples-----
Input
2 0 3 3 5 21

Output
3

Input
2 4 3 0 6 17

Output
2

Difficulty: interview

Starter code:

Solutions:
import sys, collections

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

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

def extgcd(a, b):
    if b == 0: return 1, 0
    x, y = extgcd(b, a % b)
    return y, x - a // b * y

def prime_factor(n):
    res = collections.defaultdict(int)

    i = 2
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n //= i
            cnt += 1
        if cnt > 0: res[i] = cnt
        i += 1
    if n != 1: res[n] = 1

    return res

def modinv(a, mod):
    if a == 0: return -1
    if gcd(a, mod) != 1: return -1
    return extgcd(a, mod)[0] % mod

def normalize(a1, a2):
    p1 = prime_factor(a1)
    p2 = prime_factor(a2)

    keys = list(set(p1.keys()) | set(p2.keys()))

    r1 = 1
    r2 = 1
    for k in keys:
        if p1[k] >= p2[k]:
            r1 *= k ** p1[k]
        else:
            r2 *= k ** p2[k]
    return r1, r2

def solve(a1, b1, a2, b2):
    g = gcd(a1, a2)
    if (b1 - b2) % g != 0: return -1

    a1, a2 = normalize(a1, a2)
    u = b1 % a1
    inv = modinv(a1, a2)
    v = (b2 - u) * inv % a2
    return u + v * a1

def f(x0, T, v):
    ok = 10 ** 36
    ng = -1

    while ok - ng > 1:
        mid = (ok + ng) // 2

        if x0 + T * mid >= v:
            ok = mid
        else:
            ng = mid

    return ok

a1, b1, a2, b2, L, R = map(int, input().split())

T = lcm(a1, a2)
x0 = solve(a1, b1, a2, b2)

if x0 == -1:
    print(0)
    return

x0 -= T * 10 ** 36

ok = 10 ** 60
ng = -1

while ok - ng > 1:
    mid = (ok + ng) // 2

    val = x0 + T * mid
    k = (val - b1) // a1
    l = (val - b2) // a2
    if k >= 0 and l >= 0:
        ok = mid
    else:
        ng = mid

x0 += ok * T

# L <= x0 + kT < R + 1
ans = f(x0, T, R + 1) - f(x0, T, L)

print(ans)

import sys

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

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

# ax+by=c
def extgcd(a, b, c):
    if b == 0: return c, 0
    x, y = extgcd(b, a % b, c)
    return y, x - a // b * y

def first_term(a1, b1, a2, b2):
    g = gcd(a1, a2)
    T = lcm(a1, a2)

    # s*a1+t*a2=b2-b1
    if (b2 - b1) % g != 0: return -(10 ** 100)
    x0 = extgcd(a1 // g, a2 // g, (b2 - b1) // g)[0] * a1 + b1 - T * 10 ** 30

    ok = 10 ** 60
    ng = -1

    while ok - ng > 1:
        mid = (ok + ng) // 2
        val = x0 + T * mid
        k = (val - b1) // a1
        l = (val - b2) // a2

        if k >= 0 and l >= 0:
            ok = mid
        else:
            ng = mid

    return x0 + ok * T

def f(a0, T, v):
    ok = 10 ** 36
    ng = -1

    while ok - ng > 1:
        mid = (ok + ng) // 2

        if a0 + T * mid >= v:
            ok = mid
        else:
            ng = mid

    return ok

a1, b1, a2, b2, L, R = list(map(int, input().split()))

T = lcm(a1, a2)
a0 = first_term(a1, b1, a2, b2)

if a0 == -(10 ** 100):
    print(0)
    return

print(f(a0, T, R + 1) - f(a0, T, L))


def nod(a, b):
    if b == 0:
        return a, 1, 0
    else:
        answer, x, y = nod(b, a % b)
        x1 = y
        y1 = x - (a // b) * y
        return answer, x1, y1


a1, b1, a2, b2, l, r = list(map(int, input().split()))
coeff = b1
b1, b2, l, r = b1 - coeff, b2 - coeff, max(l - coeff, 0), r - coeff
l = max(b2, l)
od, x1, y1 = nod(a1, -a2)
if b2 % od != 0 or l > r:
    print(0)
else:    
    x1, y1 = x1 * (b2 // od), y1 * (b2 // od)
    result = x1 * a1 
    raznitsa = a1 * a2 // nod(a1, a2)[0]
    otvet = 0
    if result < l:
        vsp = (l - result) // raznitsa
        if (l - result) % raznitsa != 0:
            vsp += 1
        result += vsp * raznitsa
    if result > r:
        vsp = (result - r) // raznitsa
        if (result - r) % raznitsa != 0:
            vsp += 1        
        result -= vsp * raznitsa      
    if result <= r and result >= l:
        otvet += 1
        otvet += abs(result - r) // raznitsa
        otvet += abs(result - l) // raznitsa
    print(otvet)    
    # 3 * (- 54) + 81 = 


import sys

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

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

# ax+by=c
def extgcd(a, b, c):
    if b == 0: return c, 0
    x, y = extgcd(b, a % b, c)
    return y, x - a // b * y

def first_term(a1, b1, a2, b2):
    g = gcd(a1, a2)
    T = lcm(a1, a2)

    # s*a1+t*a2=b2-b1
    if (b2 - b1) % g != 0: return -(10 ** 100)
    x0 = extgcd(a1 // g, a2 // g, (b2 - b1) // g)[0] * a1 + b1 - T * 10 ** 30

    ok = 10 ** 60
    ng = -1

    while ok - ng > 1:
        mid = (ok + ng) // 2
        val = x0 + T * mid
        k = (val - b1) // a1
        l = (val - b2) // a2

        if k >= 0 and l >= 0:
            ok = mid
        else:
            ng = mid

    return x0 + ok * T

def f(a0, T, v):
    ok = 10 ** 36
    ng = -1

    while ok - ng > 1:
        mid = (ok + ng) // 2

        if a0 + T * mid >= v:
            ok = mid
        else:
            ng = mid

    return ok

a1, b1, a2, b2, L, R = map(int, input().split())

T = lcm(a1, a2)
a0 = first_term(a1, b1, a2, b2)

if a0 == -(10 ** 100):
    print(0)
    return

print(f(a0, T, R + 1) - f(a0, T, L))

from fractions import gcd
def egcd(a, b):
    if a == 0:
        return [0, 1]
    if b == 0:
        return [1, 0]
    p = egcd(b%a, a)
    x = p[0]; y = p[1]
    return [y-x*(b//a), x]

def solve(a1, m1, a2, m2):
    sol = egcd(m1, m2)
    m1x = m1 * sol[0]
    m2y = m2 * sol[1]
    return (m1x*a2+m2y*a1)

a1, b1, a2, b2, L, R = list(map(int, input().split(' ')))
L -= b1; R -= b1; b2 -= b1; b1 = 0;
g = gcd(a1, a2)
L = max(L, max(b1, b2))
if (b2%g != 0 or L > R):
    print(0)
    quit()
rmod = a1 * a2 // g;
a1 //= g; b2 //= g; a2 //= g;
sol = solve(b1, a1, b2, a2);
mod = a1 * a2;
sol %= mod; sol *= g;
L -= sol; R -= sol;
if (L <= 0):
    lnew = L%rmod; R += lnew - L; L = lnew;
L += rmod; R += rmod;
print(R//rmod - (L-1)//rmod)



def exgcd(i, j):
    if j == 0:
        return 1, 0, i
    u, v, d = exgcd(j, i % j)
    return v, u - v * (i // j), d
ma, ra, mb, rb, L, R = list(map(int, input().split(' ')))
L = max(L, ra, rb)
if L > R:
    print(0)
    return
if ra > rb:
    ma, ra, mb, rb = mb, rb, ma, ra
_, _, md = exgcd(ma, mb)
if md != 1:
    if (rb - ra) % md != 0:
        print(0)
        return
    m = ma * mb // md
    rev, _, _ = exgcd(ma // md, mb // md)
    rev = (rev % (mb // md) + mb // md) % (mb // md)
    r = ma * (rb - ra) // md * rev + ra
    r = (r % m + m) % m
else:
    m = ma * mb
    bv, av, _ = exgcd(ma, mb)
    r = ra * mb * av + rb * ma * bv
    r = (r % m + m) % m
def calc(i):
    return (i - r) // m
print(calc(R) - calc(L - 1))


#!/usr/bin/env	python
#-*-coding:utf-8 -*-
import math
a1,b1,a2,b2,l,r=list(map(int,input().split()))
if b1<l:b1=(b1-l)%a1+l
if b2<l:b2=(b2-l)%a2+l
c=a1//math.gcd(a1,a2)*a2
m=min(1+r,c+max(b1,b2))
while b1!=b2 and m>b1:
	if b1<b2:b1=(b1-b2)%a1+b2
	else:b2=(b2-b1)%a2+b1
print((m>b1)*(1+(r-b1)//c))


import math 

# g, x, y
def gcd(a, b) :
    if a == 0 :
        return [b, 0, 1]
    l = gcd(b % a, a)
    g, x1, y1 = [int(i) for i in l]
    x = y1 - (b // a) * x1
    y = x1
    return [g, x, y]

def my_ceil(u, v) :
    if v < 0 :
        u *= -1
        v *= -1
    return math.ceil(u / v)

def my_floor(u, v) :
    if v < 0 :
        u *= -1
        v *= -1
    return math.floor(u / v)

a1, b1, a2, b2, L, R = [int(i) for i in input().split()]
A = a1
B = -a2
C = b2 - b1
g, x0, y0 = [int(i) for i in gcd(abs(A), abs(B))]

if A < 0 : x0 *= -1
if B < 0 : y0 *= -1

if C % g != 0 :
    print(0)
    return

x0 *= C // g
y0 *= C // g

le = max([
    float(R - b1 - a1 * x0) / float(a1 * B // g),
    float(y0 * a2 + b2 - R) / float(a2 * A // g)
    ])

ri = min([
    float(L - b1 - a1 * x0) / float(a1 * B // g),
    float(y0 * a2 + b2 - L) / float(a2 * A // g),
    float(-x0) / float(B // g),
    float(y0) / float(A // g)
    ])

le = int(math.ceil(le))
ri = int(math.floor(ri))

if ri - le + 1 <= 10000 :
    result = 0
    for k in range(le - 100, ri + 101) :
        X = x0 + B * k // g
        Y = y0 - A * k // g
        if X >= 0 and Y >= 0 and a1 * X + b1 >= L and a1 * X + b1 <= R :
            result += 1
    print(result)
else : 
    print(max(int(0), ri - le + 1))


from collections import defaultdict
import sys, os, math

def gcd(a1, a2):
    if a2 == 0:
        return a1
    else:
        return gcd(a2, a1 % a2)
        
# return (g, x, y) a*x + b*y = gcd(x, y)
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)
def __starting_point():
    #n, m = list(map(int, input().split()))
    a1, b1, a2, b2, L, R = map(int, input().split())
    a2 *= -1 
    LCM = a1 * a2 // gcd(a1, a2)
    if abs(b1 - b2) % gcd(a1, a2) != 0:
        print(0)
        return
    L = max([b1, b2, L])
    g, x, y = egcd(a1, a2)
    X = a1 * x * (b2 - b1) // g + b1
    X += LCM * math.ceil((L - X) / LCM)
    if L <= X <= R:
        print(max(0, (R - X) // LCM + 1))
    else:
        print(0)
__starting_point()

def extgcd(a, b):
    x, y = 0, 0
    d = a;
    if b != 0:
        d, y, x = extgcd(b, a%b)
        y -= (a//b) * x
    else:
        x, y = 1, 0
    return (d, x, y)

def main():
    a1, b1, a2, b2, L, R = map(int, input().split())
    g, k, l = extgcd(a1, a2);
    b = b2-b1;
    if (b%g != 0):
        print (0)
        return
    k *= b//g
    l *= -b//g
    low = -2**100
    high = 2**100
    while high-low > 1:
        med = (low+high)//2
        tk = k+med*a2//g
        tl = l+med*a1//g
        if (tk >= 0 and tl >= 0):
            high = med
        else:
            low = med
    k = k+high*a2//g
    x = a1*k+b1
    low = -1
    high = 2**100
    lcm = a1*a2//g
    while high - low > 1:
        med = (low+high)//2
        tx = x+med*lcm
        if tx >= L:
            high = med
        else:
            low = med
    x = x+high*lcm
    low = 0
    high = 2**100
    while high-low > 1:
        med = (low+high)//2
        tx = x+med*lcm
        if (tx <= R):
            low = med
        else:
            high = med
    if low == 0 and x > R:
        print (0)
        return
    print (low+1)
    return

def __starting_point():
    main()
__starting_point()

import math
def xgcd (b,n) :
 x0,x1,y0,y1 = 1,0,0,1
 while n != 0 :
  q,b,n = b//n , n , b % n
  x0,x1 = x1, x0-q*x1
  y0,y1 = y1,y0-q*y1
 return b,x0,y0
a,aa,b,bb,l,r = [int (x) for x in input ().split ()]
g,x,y=xgcd (a,b)
c = bb-aa
#print("c",c,g)
if c%g != 0 :
 print (0)
 exit (0)
# ax-by = cc = bb-aa
# ax-by = g(cc) = bb-aa
#print(x,y)
i = a*(x*c)//g+aa
ii = (-b*(y*c)//g)+bb
#print(a*x//g*c,b*y//g*c,aa,bb)
step = a*b//g
#print(a,x,c , " | ",b,y,c)
#print(i,ii,step)
if (ii-i) % step != 0 : 
 print(0)
 return
#print(a,x,c,aa)

#print(i,ii,step)
# shift i to la,lb
#print(i,aa,bb)
if i > max(aa,bb) :
 #print(i-max(aa,bb),step)
 i -= ((i-max(aa,bb))//step) * step
elif i < max(aa,bb) :
 i += ((max(aa,bb)-i)//step + (1 if (max(aa,bb)-i)%step!=0 else 0)) * step

f = (l-i)//step
if (l-i) % step != 0 : f+=1
f = max(f,0)
s = (r-i)//step
#print(i,step,f,s)
print (max(0,s-f+1))

#from IPython import embed
def mod(a, b):
	if b < 0:
		return mod(a,-b)
	if a >= 0:
		return a % b
	return - ((-a)%b)
def extended_gcd(a, b):
	tmp1 = a
	tmp2 = b
	xx = 0
	y = 0
	yy = 1
	x = 1
	while b != 0:
		q = a//b
		t = b
		b = mod(a,b)
		a = t
		tt = xx
		xx = x-q*xx
		x = t
		t = yy
		yy = y-q*yy
		y = t;
	assert(a == tmp1*x+tmp2*y)
	return (a,x,y)
def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def ffloor(a, b):
	if(b < 0): return ffloor(-a,-b);
	return a//b
def cceil( a,  b):
	if(b < 0): return cceil(-a,-b);
	if a % b == 0: 
		return a//b
	return a//b+1;
	


def main():
	s = input()
	a1, b1, a2, b2, L, R = [int(i) for i in s.split()]

	if b2 < b1:
		a1, a2 , b1, b2 = a2, a1 , b2, b1

	d,x,y = xgcd(a1,-a2)#extended_gcd(a1,-a2)
	if(d < 0):
		d *= -1
		x *= -1
		y *= -1
	
	if (b2 - b1) % d !=  0: 
		print(0)
		return

	#print(d,x,y)
	fact = (b2-b1)//d
	x *= fact
	y *= fact

	c1 = a2//d;
	c2 = a1//d;


	tope1 = ffloor(R-b1-a1*x, a1*c1);
	bajo1 = cceil(L-b1-a1*x,c1*a1);
	bajo2 = cceil(L-b2-a2*y,c2*a2);
	tope2 = ffloor(R-b2-a2*y, a2*c2);

	bajo3 = max(cceil(-x,c1),cceil(-y,c2));

	#print(R-b1-a1*x) /( a1*c1) ,(R-b2-a2*y)/ (a2*c2)
	#print(L-b1-a1*x)/(c1*a1) ,(L-b2-a2*y)/(c2*a2)
	#print(-x/c1,-y/c2)
	#print(bajo1,tope1)
	
	#print(bajo2,tope2)
	#print(bajo3)
	bajo = max(bajo1,bajo2,bajo3);
	tope = min(tope1,tope2);
	print(max(0,tope+1-bajo))
	#embed()
main()

#from IPython import embed

def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def ffloor(a, b):
	if(b < 0): return ffloor(-a,-b);
	return a//b
def cceil( a,  b):
	if(b < 0): return cceil(-a,-b);
	if a % b == 0: 
		return a//b
	return a//b+1;
	


def main():
	s = input()
	a1, b1, a2, b2, L, R = [int(i) for i in s.split()]

	if b2 < b1:
		a1, a2 , b1, b2 = a2, a1 , b2, b1

	d,x,y = xgcd(a1,-a2)#extended_gcd(a1,-a2)
	if(d < 0):
		d *= -1
		x *= -1
		y *= -1
	
	if (b2 - b1) % d !=  0: 
		print(0)
		return

	#print(d,x,y)
	fact = (b2-b1)//d
	x *= fact
	y *= fact

	c1 = a2//d;
	c2 = a1//d;


	tope1 = ffloor(R-b1-a1*x, a1*c1);
	bajo1 = cceil(L-b1-a1*x,c1*a1);
	bajo2 = cceil(L-b2-a2*y,c2*a2);
	tope2 = ffloor(R-b2-a2*y, a2*c2);

	bajo3 = max(cceil(-x,c1),cceil(-y,c2));

	bajo = max(bajo1,bajo2,bajo3);
	tope = min(tope1,tope2);
	print(max(0,tope+1-bajo))
	#embed()
main()

a1, b1, a2, b2, L, R = list(map(int, input().split()))

def xgcd(a,b):
    prevx, x = 1, 0
    prevy, y = 0, 1
    while b:
        q = a // b
        x, prevx = prevx - q * x, x
        y, prevy = prevy - q * y, y
        a, b = b, a % b

    return a, prevx, prevy

g, x, y = xgcd(a1, -a2)

if (b2 - b1) // g < 0:    
    g, x, y = -g, -x, -y

if abs(b2 - b1) % abs(g) > 0:
    print(0)
else:
    a2g, a1g = a2 // abs(g), a1 // abs(g)

    x *= (b2 - b1) // g
    y *= (b2 - b1) // g

    if x < 0:
        y += ((abs(x) + a2g - 1) // a2g) * a1g
        x += ((abs(x) + a2g - 1) // a2g) * a2g      

    if y < 0:
        x += ((abs(y) + a1g - 1) // a1g) * a2g
        y += ((abs(y) + a1g - 1) // a1g) * a1g

    if x >= 0 and y >= 0:
        k = min(x // a2g, y // a1g)
        x -= k * a2g
        y -= k * a1g

    res = a1 * x + b1
    lcm = a1 * a2 // abs(g)

    L, R = max(0, L - res), R - res

    if R < 0:
        print(0)
    else:
        print(R // lcm - L // lcm + (L % lcm == 0))



from math import gcd
def exd_gcd(a, b):
  # always return as POSITIVE presentation
  if a % b == 0:
    return 0, (1 if b > 0 else -1)
  x, y = exd_gcd(b, a % b)
  return y, x - a // b * y
def interval_intersect(a, b, c, d):
  if b <= a or d <= c:
    return 0
  if c < a:
    a, b, c, d = c, d, a, b
  if c < b:
    return min(b, d) - c
  else:
    return 0
def ceil(a, b):
  return (a + b - 1) // b

a1, b1, a2, b2, L, R = list(map(int, input().split()))
g = gcd(a1, a2)
if (b1 - b2) % g != 0:
  print(0)
  return
k, l = exd_gcd(a1, a2)
l = -l
k *= (b2 - b1) // g
l *= (b2 - b1) // g
d1 = a2 // g
d2 = a1 // g
assert(k * a1 + b1 == l * a2 + b2)
arb = 3238
assert((k + arb * d1) * a1 + b1 == (l + arb * d2) * a2 + b2)
L1, R1 = ceil(max(0, ceil(L - b1, a1)) - k, d1), ((R - b1) // a1 - k) // d1
L2, R2 = ceil(max(0, ceil(L - b2, a2)) - l, d2), ((R - b2) // a2 - l) // d2
print(interval_intersect(L1, R1 + 1, L2, R2 + 1))


from fractions import gcd
a1,b1,a2,b2,l,r=list(map(int,input().split()))

if b1<l:
    b1=(b1-l)%a1+l
if b2<l:
    b2=(b2-l)%a2+l
ks1=(l-b1)/a1
ke1=(r-b1)/a1
ks2=(l-b2)/a2
ke2=(r-b2)/a2

g=gcd(a1,a2)
var=a1/g*a2
lst1=[]
lst2=[]
ks1=max(b1,b2)

m=min(1+r,var+ks1)
while b1!=b2 and m>b1:
    if b1<b2:
        b1=(b1-b2)%a1+b2
    else:
        b2=(b2-b1)%a2+b1
if(m>b1):
    print(int(1+(r-b1)//var))
else:
    print ("0")





def gcd(a, b):
    if a==0:
        return (b, 0, 1)
    g, x1, y1 = gcd(b%a, a)
    x = y1 - (b // a) * x1
    y = x1
    return (g, x, y)
	
def solve(a, b, x, y, r):
    k = (r-x)//a
    y = (y-x) % b
    
    gg, X, Y = gcd(a, b)
    #print(gg, X, Y, y, a, b)
    if y % gg != 0:
        return 0
    X *= y // gg
    dd = b//gg
    if X >= 0:
        X -= (X//dd) * dd
    else:
        g = X//dd
        if g * dd > X:
            g += 1
        X -= g * dd
    
    if X < 0:
        X += dd
    elif X >= dd:
        X -= dd
    
    if X > k:
        return 0
    return (k-X)//dd + 1


a1, b1, a2, b2, L, R = map(int, input().split())
d1 = (L-b1)//a1
if d1 < 0:
    d1 = 0
d1 *= a1
d1 += b1
d2 = (L-b2)//a2
if d2 < 0:
    d2 = 0
d2 *= a2
d2 += b2

while d1 < L:
    d1 += a1
while d2 < L:
    d2 += a2

#print(d1, d2, L, R)

if R < max(d1, d2):
    print(0)
else:
    
    if d1 > d2 or (d1 == d2 and a1 < a2):
        print(solve(a1, a2, d1, d2, R))
    else:
        print(solve(a2, a1, d2, d1, R))

import math

a1, b1, a2, b2, l, r = list(map(int, input().split()))
if b1 < l:
  b1 = (b1 - l) % a1 + l
if b2 < l:
  b2 = (b2 - l) % a2 + l
c = a1 // math.gcd(a1, a2) * a2
m = min(1 + r, c + max(b1, b2))
while b1 != b2 and m > b1:
  if b1 < b2:
    b1 = (b1 - b2) % a1 + b2
  else:
    b2 = (b2 - b1) % a2 + b1
print((m > b1) * (1 + (r - b1) // c))


import sys
# Uz ma to pretekanie nebavi!!!

def gcd(a, b):
    if b == 0:
        return [a, 1, 0]
    c = a%b
    [g, x1, y1] = gcd(b, c)
    x = y1
    y = x1 - y1 * (a//b)
    return [g, x, y]

a1, b1, a2, b2, l, r = [int(i) for i in input().split(" ")]
if max(b1, b2) > r:
    print(0)
    return

l = max(l, b1, b2)
[g, xg, yg] = gcd(a1, a2)
if (b2 - b1) % g == 0:
    xg *= (b2 - b1) // g
else:
    print(0)
    return
lcm = (a1 * a2) // g
val = xg * a1 + b1
if val >= l:
    val -= (((val - l) // lcm) + 1) * lcm
    
print(((r - val) // lcm) - ((l - val - 1) // lcm))