Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.


-----Input-----

The first line of the input contains a single integer x (1 ≤ x ≤ 10^18) — the number of squares inside the tables Spongebob is interested in.


-----Output-----

First print a single integer k — the number of tables with exactly x distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.


-----Examples-----
Input
26

Output
6
1 26
2 9
3 5
5 3
9 2
26 1

Input
2

Output
2
1 2
2 1

Input
8

Output
4
1 8
2 3
3 2
8 1



-----Note-----

In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total. [Image] 

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total. [Image]

Difficulty: HARD
Tags: Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
n = int(input())
(i, t, s) = [0] * 3
r = []
while 1 > 0:
	i += 1
	n -= i * i
	if n < 0:
		break
	t += i
	m = n // t
	if m * t != n:
		continue
	r.append((i, m + i))
	if m > 0:
		r.append((m + i, i))
print(len(r))
r.sort()
for (m, n) in r:
	print('%d %d' % (m, n))


def solve(x):
	res = [(1, x)]
	if x != 1:
		res.append((x, 1))
	(index, a, b) = (1, 1, 0)
	while True:
		b += a
		index += 1
		a += index
		if a * index - b > x:
			break
		if (x + b) % a == 0:
			m = (x + b) // a
			res.append((index, m))
			if index != m:
				res.append((m, index))
	res.sort()
	print(len(res))
	for ares in res:
		print(ares[0], ares[1])

def __starting_point():
	x = int(input())
	solve(x)
__starting_point()


x = int(input()) * 6
(n, equ, ans) = (0, False, [])
while True:
	n += 1
	if n * (n + 1) * (2 * n - 1) > x:
		break
	if x % n != 0:
		continue
	if x % (n + 1) != 0:
		continue
	m = x // n // (n + 1) + n - 1
	if m % 3 != 0:
		continue
	m = m // 3
	if n <= m:
		ans.append([n, m])
		if n == m:
			equ = True
print(len(ans) * 2 - equ)
for p in ans:
	print('%d %d' % (p[0], p[1]))
if equ:
	ans.pop()
ans.reverse()
for p in ans:
	p.reverse()
	print('%d %d' % (p[0], p[1]))


from functools import reduce
from itertools import islice, product
from operator import mul

def prod(iterable, start=1):
	return reduce(mul, iterable, start)

def isqrt(n):
	(x, px, nx) = (0, 0, n)
	while nx not in (x, px):
		(px, x) = (x, nx)
		nx = (x + n // x) // 2
	return min(x, nx)

def relevant_factors(n):
	for i in range(2, 2000000):
		if i ** 2 > n:
			break
		c = 0
		(q, r) = divmod(n, i)
		while not r:
			c += 1
			n = q
			(q, r) = divmod(n, i)
		if c:
			yield (i, c)
	if n > 1:
		sn = isqrt(n)
		if sn * sn == n:
			yield (sn, 2)
		elif sn * (sn + 1) == n:
			yield ((sn, 1), (sn + 1, 1))
		else:
			yield (n, 1)

def divisors(fp):
	return sorted((prod(t) for t in product(*[powers(f, e + 1) for (f, e) in fp])))

def powers(b, e):
	k = 1
	for _ in range(e):
		yield k
		k *= b

def tables(n):
	if n == 1:
		return [(1, 1)]
	t = set()
	n6 = 6 * n
	for a in divisors(relevant_factors(n6)):
		(q, r) = divmod(n6, a * (a + 1))
		if r:
			continue
		(b, r) = divmod(q + a - 1, 3)
		if r:
			continue
		if b < a:
			continue
		t.add((a, b))
		t.add((b, a))
	return sorted(t)
n = int(input())
ts = tables(n)
print(len(ts))
for t in ts:
	print('{} {}'.format(*t))


s = int(input())
(a, b) = ([], [])
for n in range(1, 1450000):
	u = 6 * s - n * (n - 1) * (n + n - 1) + 3 * (n - 1) * n * n
	v = 6 * n * n - 3 * (n - 1) * n
	if u % v == 0:
		u //= v
		if n <= u:
			a += [(n, u)]
			if n < u:
				b += [(u, n)]
		else:
			break
print(len(a) + len(b))
for e in a:
	print(*e)
for e in reversed(b):
	print(*e)


(n, i, t, r) = (int(input()), 0, 0, [])
while 1:
	i += 1
	n -= i * i
	if n < 0:
		break
	t += i
	m = n // t
	r += [(m + i, i), (i, m + i)][m == 0:] * (m * t == n)
print(len(r))
for p in sorted(r):
	print('%d %d' % p)


x = int(input())

def solve(x):
	count = 0
	lst = []
	x6 = x * 6
	for n in range(1, x + 1):
		(t, r) = divmod(x6, n * (n + 1))
		if t < 2 * n + 1:
			break
		if r:
			continue
		(m, r) = divmod(t + n - 1, 3)
		if r:
			continue
		count += 2
		lst.append((n, m))
	(nn, mm) = lst[-1]
	if nn == mm:
		count -= 1
	print(count)
	for (n, m) in lst:
		print(n, m)
	if nn != mm:
		print(mm, nn)
	lst.reverse()
	for (n, m) in lst[1:]:
		print(m, n)
solve(x)


import itertools
import math
x = int(input())
kmax = math.floor((3 * x) ** (1 / 3))
ans = []
for i in range(1, kmax + 1):
	if 6 * x % (i * (i + 1)) == 0:
		s = 6 * x // (i * (i + 1)) + i - 1
		if s % 3 == 0:
			ans.append((i, s // 3))
res = 2 * len(ans) - 1 if ans[-1][0] == ans[-1][1] else 2 * len(ans)
print(res)
for pair in ans[:-1]:
	print(pair[0], pair[1])
if res % 2 == 0:
	print(ans[-1][0], ans[-1][1])
for pair in reversed(ans):
	print(pair[1], pair[0])


x = int(input())
a = 1
ans = []
t = set()
while a * a * a <= 3 * x:
	if a in t:
		break
	if ((a * a * a - a) // 3 + 2 * x) % (a * a + a) == 0:
		b = ((a * a * a - a) // 3 + 2 * x) // (a * a + a)
		ans.append([a, b])
		if a != b:
			ans.append([b, a])
		t.add(a)
		t.add(b)
	a += 1
print(len(ans))
ans = sorted(ans, key=lambda student: student[0])
for i in ans:
	c = []
	c.append(str(i[0]))
	c.append(str(i[1]))
	print(' '.join(c))


from itertools import chain, combinations
from functools import reduce
from collections import defaultdict

def res(m, n):
	k = min(m, n)
	return (1 + k) * (k + 2 * k ** 2 - 3 * k * (m + n) + 6 * m * n) // 6

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

def prod(it):
	r = 1
	for elem in it:
		r *= elem
	return r

def factorGenerator(n):
	res = defaultdict(lambda : 0)
	for p in range(2, 10 ** 6 + 1):
		while n % p == 0:
			res[p] += 1
			n = n // p
	return res

def divisorGen(n):
	factors = list(factorGenerator(n).items())
	nfactors = len(factors)
	f = [0] * nfactors
	while True:
		yield reduce(lambda x, y: x * y, [factors[x][0] ** f[x] for x in range(nfactors)], 1)
		i = 0
		while True:
			f[i] += 1
			if f[i] <= factors[i][1]:
				break
			f[i] = 0
			i += 1
			if i >= nfactors:
				return

def res2(x):
	r = []
	x6 = 6 * x
	divisors = set(divisorGen(x6))
	for m in divisors:
		a = x6 // m
		if a % (m + 1) != 0:
			continue
		b = a // (m + 1)
		c = b + m - 1
		if c % 3 != 0:
			continue
		n = c // 3
		if n < m:
			continue
		if res(m, n) != x:
			continue
		r.append((m, n))
	return r
x = int(input())
r = res2(x)
r = r + [(n, m) for (m, n) in r]
r = sorted(set(r))
print(len(r))
for (m, n) in r:
	print('%d %d' % (m, n))


(p, q) = (int(input()), 1)
(t, n) = ([], 1)
while p > n * q:
	if p % q == 0:
		t.append((p // q, n))
	n += 1
	q += n
	p += (n * n - n) // 2
t += [(m, n) for (n, m) in t]
if p == n * q:
	t.append((n, n))
print(len(t))
for (n, m) in sorted(t):
	print(n, m)


import itertools as it
import functools
import operator
import collections
import math
import sys

def solve(x):

	def find_p(n):
		return (6 * x // (n * (n + 1)) - 2 * n - 1) // 3

	def f(n, p):
		return n * (n + 1) * (2 * n + 3 * p + 1) - 6 * x
	result = []
	for n in it.count(1):
		p = find_p(n)
		if p < 0:
			break
		if f(n, p) == 0:
			result.append((n, n + p))
			if p > 0:
				result.append((n + p, n))
	result.sort()
	return result

def main():
	x = int(input())
	results = solve(x)
	print(len(results))
	for res in results:
		print(*res)
main()


def main():
	x = int(input())
	l = squares(x)
	last = l[len(l) - 1]
	if last[0] != last[1]:
		print(2 * len(l))
	else:
		print(2 * len(l) - 1)
	for pair in l:
		print(pair[0], pair[1])
	if last[0] != last[1]:
		for pair in l[::-1]:
			print(pair[1], pair[0])
	else:
		revL = l[::-1]
		for pair in revL[1:]:
			print(pair[1], pair[0])

def squares(x):
	if x == 1:
		return [(1, 1)]
	result = []
	cubeRoot = int((6 * x) ** (1 / 3))
	n = 1
	while n <= cubeRoot:
		y = 6 * x
		temp = n * (n + 1)
		if y % temp == 0:
			y //= temp
			y += n - 1
			if y % 3 == 0:
				m = y // 3
				if m >= n:
					result += [(n, m)]
		n += 1
	return result
main()


x = 6 * int(input())
r = []
for m in range(1, 10 ** 7):
	d = m * (m + 1)
	if d * m > x:
		break
	if x % d != 0:
		continue
	mx = x // d + m - 1
	if mx % 3 != 0:
		continue
	nx = mx // 3
	if nx > m:
		r.append((m, nx))
		r.append((nx, m))
	elif nx == m:
		r.append((m, nx))
print(len(r))
for sol in sorted(r):
	print(str(sol[0]) + ' ' + str(sol[1]))


import unittest
import sys

class Squares:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.n] = map(int, uinput().split())

	def calculate(self):
		result = []
		n = 1
		while n * n * (n - 1) // 6 < self.n:
			a = n * (n + 1) // 2
			b = n * (n - 1) * (n + 1) // 6
			m = self.n + b
			k = m // a
			if n <= k and m % a == 0:
				result.append((n, k))
			n += 1
		result2 = list(result)
		result2 += [(b, a) for (a, b) in reversed(result) if a != b]
		s = str(len(result2)) + '\n'
		s += '\n'.join([str(a) + ' ' + str(b) for (a, b) in result2])
		return s

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '26'
		d = Squares(test)
		self.assertEqual(d.n, 26)
		self.assertEqual(Squares(test).calculate(), '6\n1 26\n2 9\n3 5\n5 3\n9 2\n26 1')
		test = '0'
		self.assertEqual(Squares(test).calculate(), '0\n')
		test = ''
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Squares(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Squares().calculate())


x = int(input())
if x == 1:
	a = [(1, 1)]
a = []
cor = int((6 * x) ** (1 / 3))
n = 1
while n <= cor:
	y = 6 * x
	tec = n * (n + 1)
	if y % tec == 0:
		y //= tec
		y += n - 1
		if y % 3 == 0:
			m = y // 3
			if m >= n:
				a += [(n, m)]
	n += 1
p = a[len(a) - 1]
if p[0] != p[1]:
	print(2 * len(a))
else:
	print(2 * len(a) - 1)
for i in a:
	print(i[0], i[1])
if p[0] != p[1]:
	for i in a[::-1]:
		print(i[1], i[0])
else:
	for i in a[::-1][1:]:
		print(i[1], i[0])


n = int(input())
ans = []
for i in range(1, 1442250 + 10):
	t = i * (i + 1) // 2
	(j, mod) = divmod(n + (i - 1) * t // 3, t)
	if i > j:
		break
	if mod == 0:
		ans.append((i, j))
		if i != j:
			ans.append((j, i))
ans.sort()
print(len(ans))
for (x, y) in ans:
	print(x, y)


__author__ = 'MoonBall'
import sys
T = 1

def process():
	ans = []
	N = int(input())
	for i in range(1, 3000000):
		a = N + i * (i - 1) * (i + 1) // 6
		(j, mod) = divmod(a, i * (i + 1) // 2)
		if i > j:
			break
		if mod:
			continue
		ans.append((i, j))
		if i != j:
			ans.append((j, i))
	ans.sort()
	print(len(ans))
	for (i, j) in ans:
		print(i, j)
for _ in range(T):
	process()


n = int(input())
i = 0
s = 0
t = 0
x = 0
f = 0
res1 = []
res2 = []
while n >= 0:
	i = i + 1
	n = n - i * i
	if n < 0:
		break
	t = t + i
	m = n // t
	if m * t != n:
		continue
	else:
		res1.append(i)
		res2.append(m + i)
		x = x + 1
		if m == 0:
			f = 1
print(str(int(2 * x - f)))
for i in range(x):
	print(str(int(res1[i])) + ' ' + str(int(res2[i])))
res1.reverse()
res2.reverse()
for i in range(x):
	if res1[i] != res2[i]:
		print(str(int(res2[i])) + ' ' + str(int(res1[i])))


x = int(input())
i = 1
nmList = []
while True:
	if i * (i + 1) * (2 * i + 1) > 6 * x:
		break
	if 6 * x % (i * (i + 1)) == 0 and (6 * x // (i * (i + 1)) - (2 * i + 1)) % 3 == 0:
		nmList.append((i, i + (6 * x // (i * (i + 1)) - (2 * i + 1)) // 3))
	i += 1
number = 0
for elem in nmList:
	if elem[0] != elem[1]:
		number += 2
	else:
		number += 1
print(number)
for elem in nmList:
	print(str(elem[0]) + ' ' + str(elem[1]))
for i in range(len(nmList) - 1, -1, -1):
	elem = nmList[i]
	if elem[0] == elem[1]:
		continue
	print(str(elem[1]) + ' ' + str(elem[0]))


x = int(input())
res = []
ok = -1
for i in range(1, 3000001):
	m = i
	tmp = (m - 1) * (m + 1) * m // 6 + x
	if tmp * 2 % (m * (m + 1)) == 0:
		n = int(tmp * 2 // (m * (m + 1)))
		if n > m:
			res.append([i, n])
		if n == m and ok == -1:
			ok = len(res)
			res.append([i, i])
d = 0 if ok == -1 else 1
print(len(res) * 2 - d)
for i in range(len(res)):
	print(str(res[i][0]) + ' ' + str(res[i][1]))
for i in range(len(res)):
	if len(res) - i - 1 != ok:
		print(str(res[len(res) - i - 1][1]) + ' ' + str(res[len(res) - i - 1][0]))


from collections import Counter

def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def printlist(l):
	print(' '.join([str(x) for x in l]))
n = it()
L = []
R = []
for i in range(1, int((3 * n) ** (1 / 3)) + 1):
	if 6 * n % (i * (i + 1)) == 0:
		if (6 * n // (i * (i + 1)) + i - 1) % 3 == 0:
			t = (6 * n // (i * (i + 1)) + i - 1) // 3
			L.append([i, t])
			if i < t:
				R.insert(0, [t, i])
result = L + R
print(len(result))
for i in result:
	printlist(i)