While playing in the plains, Chef found a point A with coordinates (X, Y). 

Chef is interested in finding the number of [straight lines] passing through the point A such that their [intercepts] on both axes are positive integers. 

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

- First and only line of input contains two integers X and Y - the coordinates of the point A.

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

- For each test case, print an integer - the number of lines satisfying the given conditions.

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

$1 ≤ X ≤ 10^{12}$
$1 ≤ Y ≤ 10^{12}$

----- Sample Input 1 ------ 
3 2
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
There are $4$ lines satisfying all the conditions. These lines are:

![image]

----- Sample Input 2 ------ 
1 2
----- Sample Output 2 ------ 
2
----- explanation 2 ------ 
There are $2$ such lines, which are :

![image]

----- Sample Input 3 ------ 
28 206
----- Sample Output 3 ------ 
16
----- explanation 3 ------ 
There are $16$ such lines.

Difficulty: VERY_HARD
Tags: Geometry

Mathematics

Starter code:

Solutions:
import math
(x, y) = map(int, input().split())
n = x * y
ans = 1
for i in range(2, int(math.sqrt(n)) + 2):
	if i > math.sqrt(n) + 1:
		break
	if n % i == 0:
		count = 0
		while n % i == 0:
			n = n // i
			count += 1
		ans *= count + 1
if n > 1:
	ans *= 2
print(ans)


import math

def printDivisors(n):
	l = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(int(n / i))
		i = i + 1
	return l
(X, Y) = input().split()
X = int(X)
Y = int(Y)
a = printDivisors(X)
b = printDivisors(Y)
D = {}
for i in b:
	for j in a:
		if i / j not in D:
			D[i / j] = 1
print(len(D))


from math import gcd, sqrt

def divisorGenerator(n):
	large_divisors = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			yield i
			if i * i != n:
				large_divisors.append(n // i)
	for divisor in reversed(large_divisors):
		yield divisor
(X, Y) = list(map(int, input().split()))
div_X = list(divisorGenerator(X))
div_Y = list(divisorGenerator(Y))
answer = 0
for p in div_Y:
	for q in div_X:
		if gcd(p, q) == 1:
			answer += 1
print(answer)


import math
(M, M1) = (1000000007, 998244353)

def factors(x):
	ans = set()
	for i in range(1, int(math.sqrt(x)) + 2):
		if x % i == 0:
			ans.add(i)
			ans.add(x // i)
	ans = list(ans)
	return ans

def main():
	(x, y) = input().split()
	res = set()
	facx = factors(int(x))
	facy = factors(int(y))
	for i in facx:
		for j in facy:
			res.add(i / j)
	print(len(res))
main()


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def factors(x):
	ans = set()
	for i in range(1, int(math.sqrt(x)) + 2):
		if x % i == 0:
			ans.add(i)
			ans.add(x // i)
	ans = list(ans)
	return ans

def main():
	how_much_noob_I_am = 1
	for _ in range(how_much_noob_I_am):
		(x, y) = sep()
		res = set()
		facx = factors(x)
		facy = factors(y)
		for i in facx:
			for j in facy:
				res.add(i / j)
		print(len(res))
main()


def pr(n, dt):
	n1 = n
	if n % 2 == 0:
		while n % 2 == 0:
			dt[2] = dt.get(2, 0) + 1
			n //= 2
	for i in range(3, int(n1 ** 0.5) + 2, 2):
		if n % i == 0:
			while n % i == 0:
				dt[i] = dt.get(i, 0) + 1
				n //= i
	if n != 1:
		dt[n] = dt.get(n, 0) + 1
	return dt
(x, y) = map(int, input().split())
d = {}
d = pr(x, d)
d = pr(y, d)
ans = 1
for ele in d:
	ans *= d[ele] + 1
print(ans)


from collections import defaultdict
from math import sqrt
(x, y) = map(int, input().split())
mp = defaultdict(int)
for i in range(2, int(sqrt(x)) + 1):
	while x % i == 0:
		mp[i] += 1
		x //= i
if x > 1:
	mp[x] += 1
x = y
for i in range(2, int(sqrt(x)) + 1):
	while x % i == 0:
		mp[i] += 1
		x //= i
if x > 1:
	mp[x] += 1
ans = 1
for el in mp:
	ans *= mp[el] + 1
print(ans)


d = dict()

def cal(n):
	i = 2
	while n > 1:
		if n % i == 0:
			if i in d.keys():
				d[i] += 1
			else:
				d[i] = 1
			n //= i
		elif i == 2:
			i += 1
		else:
			i += 2
		if i > 1000003:
			if n > 1000003:
				if n in d.keys():
					d[n] += 1
				else:
					d[n] = 1
			break
(x, y) = map(int, input().split())
cal(x)
cal(y)
ans = 1
for (x, y) in d.items():
	ans *= y + 1
print(ans)


from collections import defaultdict
from functools import reduce
from operator import mul
pe = defaultdict(int)
for xy in map(int, input().split()):
	p = 2
	while p * p <= xy:
		while xy % p == 0:
			pe[p] += 1
			xy //= p
		p += 1
	if xy > 1:
		pe[xy] += 1
print(reduce(mul, [e + 1 for (p, e) in pe.items()], 1))


from collections import defaultdict
pe = defaultdict(int)
for xy in map(int, input().split()):
	p = 2
	while p * p <= xy:
		while xy % p == 0:
			pe[p] += 1
			xy //= p
		p += 1
	if xy > 1:
		pe[xy] += 1
ans = 1
for (p, e) in pe.items():
	ans *= e + 1
print(ans)


from collections import defaultdict
pe = defaultdict(int)

def factorize(x):
	p = 2
	while p * p <= x:
		while x % p == 0:
			pe[p] += 1
			x //= p
		p += 1
	if x > 1:
		pe[x] += 1
(x, y) = map(int, input().split())
factorize(x)
factorize(y)
ans = 1
for (p, e) in pe.items():
	ans *= e + 1
print(ans)


(X, Y) = map(int, input().split())
p = X * Y
x = 2
ans = 1
while x * x <= p:
	if p % x == 0:
		q = 1
		while True:
			p //= x
			q += 1
			if p % x != 0:
				break
		ans *= q
	x += 1
if p > 1:
	ans *= 2
print(ans)


from collections import Counter
from math import gcd

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)
(x, y) = map(int, input().split())
cnt = prime_factors(x * y)
num = 1
for val in cnt.values():
	num *= val + 1
print(num)


from collections import Counter

def factorize(x):
	factors = Counter()
	p = 2
	while p * p <= x:
		if x % p == 0:
			while x % p == 0:
				factors[p] += 1
				x //= p
		p += 1
	if x > 1:
		factors[x] = 1
	return factors
(x, y) = map(int, input().split())
c = factorize(x) + factorize(y)
ans = 1
for (k, v) in c.items():
	ans *= v + 1
print(ans)


from math import sqrt
from sys import stdin
input = stdin.readline

def factors(n):
	f = set()
	step = 2 if n % 2 else 1
	for x in range(1, int(sqrt(n)) + 1, step):
		(q, r) = divmod(n, x)
		if r == 0:
			f.add(x)
			f.add(q)
	return sorted(list(f))

def solve(X, Y):
	A = factors(X)
	B = factors(Y)
	fractions = set()
	for p in A:
		for q in B:
			fractions.add(p / q)
	return len(fractions)
(X, Y) = [int(x) for x in input().strip().split()]
print(solve(X, Y))


def factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	return result
(x, y) = map(int, input().split())
f = x * y
f1 = factors(x)
f2 = factors(y)
lst2 = []
for j in f1:
	for k in f2:
		lst2.append(j * k)
		lst2.append(j)
		lst2.append(k)
lst2 = list(set(lst2))
c = 0
lst1 = []
ele = y / x
for j in lst2:
	if -(y / j) <= ele:
		c += 1
print(c)