Given two integers A and B, find the count of integers X \in [L, R] such that at least one of the following is true:
X and A are [coprime]
X and B are [coprime]

------ Input Format ------ 

- The first and only line of input contains four integers A,B,L, and R: as given in the problem statement.

------ Output Format ------ 

- Print a single integer denoting the count of integers X satisfying the condition.

------ Constraints ------ 

$1 ≤ A,B ≤ 10^{9}$
$1 ≤ L ≤ R ≤ 10^{18}$

----- Sample Input 1 ------ 
6 15 1 10

----- Sample Output 1 ------ 
6

----- explanation 1 ------ 
There are $6$ numbers that satisfy the condition: $1,2,4,5,7,8$.

----- Sample Input 2 ------ 
235714494 193478285 2 100000000000

----- Sample Output 2 ------ 
65435081000

----- explanation 2 ------

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
possible_pfs = [2, 3] + [6 * x + d for x in range(1, 5271) for d in [-1, 1]]

def LII():
	return [int(x) for x in input().split()]

def ceilq(a, b):
	return (a + b - 1) // b

def prime_factors(n):
	pfs = set({})
	for p in possible_pfs:
		if n % p == 0:
			pfs.add(p)
			while n % p == 0:
				n //= p
		if p * p > n:
			break
	if n > 1:
		pfs.add(n)
	return pfs

def copr(l, r, x):
	if x:
		y = x.copy()
		p = y.pop()
		return copr(l, r, y) - copr(ceilq(l, p), r // p, y)
	else:
		return r - l + 1
(a, b, l, r) = LII()
pfs_a = prime_factors(a)
pfs_b = prime_factors(b)
pfs_ab = pfs_a | pfs_b
print(copr(l, r, pfs_a) + copr(l, r, pfs_b) - copr(l, r, pfs_ab))


def prime_factor(x):
	i = 2
	primes = []
	while i * i <= x:
		if x % i == 0:
			primes.append(i)
			while x % i == 0:
				x //= i
		i += 1
	if x > 1:
		primes.append(x)
	return primes

def calc(l, r, primes):
	sz = len(primes)
	ans = 0
	for mask in range(1, 2 ** sz):
		num = 1
		for i in range(sz):
			if mask & 2 ** i:
				num *= primes[i]
		parity = bin(mask)[2:].count('1') % 2
		ct = r // num - (l - 1) // num
		if parity == 1:
			ans += ct
		else:
			ans -= ct
	return ans
(a, b, l, r) = map(int, input().split())
ans = calc(l, r, prime_factor(a)) + calc(l, r, prime_factor(b)) - calc(l, r, list(set(prime_factor(a) + prime_factor(b))))
print(r - l + 1 - ans)


from sys import stdin
from itertools import chain, combinations
import math

def get_ints():
	return list(map(int, stdin.readline().strip().split()))

def primeFactors(n):
	x = set()
	while n % 2 == 0:
		x.add(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			x.add(int(i))
			n = n / i
	if n > 2:
		x.add(int(n))
	return x

def no_div_by(set_of_primes, L, R):
	prod = 1
	for x in set_of_primes:
		prod *= x
	return R // prod - (L - 1) // prod

def powerset(iterable):
	s = list(iterable)
	return chain.from_iterable((combinations(s, r) for r in range(2, len(s) + 1)))

def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
(A, B, L, R) = get_ints()
primes_A = primeFactors(A)
primes_B = primeFactors(B)
primes_C = set()
primes_C.update(primes_A)
primes_C.update(primes_B)
number_of_coprimes = 2 * (R - L + 1)
P_A = [[x] for x in primes_A]
P_A.extend(list(powerset(primes_A)))
for i in P_A:
	number_of_coprimes += (-1) ** len(i) * no_div_by(i, L, R)
P_B = [[x] for x in primes_B]
P_B.extend(list(powerset(primes_B)))
for i in P_B:
	number_of_coprimes += (-1) ** len(i) * no_div_by(i, L, R)
number_of_common = R - L + 1
P_C = [[x] for x in primes_C]
P_C.extend(list(powerset(primes_C)))
for i in P_C:
	number_of_common += (-1) ** len(i) * no_div_by(i, L, R)
print(int(number_of_coprimes - number_of_common))


import math

def bunkai(a):
	s = []
	k = 2
	while k <= a:
		if a % k == 0:
			s.append(k)
			while True:
				a //= k
				if a % k != 0:
					break
		k += 1
	return s

def main():
	(a, b, l, r) = map(int, input().split())
	af = bunkai(a)
	bf = bunkai(b)
	g = list(set(af + bf))
	g.sort()
	count = 0
	ans = 0
	for i in range(1, 2 ** len(af)):
		k = 0
		m = 1
		for j in range(len(af)):
			if i & 1 << j:
				k += 1
				m = m * af[j] // math.gcd(m, af[j])
		count += (-1) ** ((k + 1) % 2) * (r // m - (l - 1) // m)
	ans += r - l + 1 - count
	count = 0
	for i in range(1, 2 ** len(bf)):
		k = 0
		m = 1
		for j in range(len(bf)):
			if i & 1 << j:
				k += 1
				m = m * bf[j] // math.gcd(m, bf[j])
		count += (-1) ** ((k + 1) % 2) * (r // m - (l - 1) // m)
	ans += r - l + 1 - count
	countw = 0
	for i in range(1, 2 ** len(g)):
		k = 0
		m = 1
		for j in range(len(g)):
			if i & 1 << j:
				k += 1
				m = m * g[j] // math.gcd(m, g[j])
		countw += (-1) ** ((k + 1) % 2) * (r // m - (l - 1) // m)
	ans = ans - (r - l + 1 - countw)
	print(ans)
main()