Given a positive integer, $n$, find and print the number of pairs of positive integers $(a,b)$, where $a<b$, that exist such that the equation $x\cdot a+y\cdot b=n$ (where $\boldsymbol{x}$ and $y$ are positive integers) has at least one solution.

Input Format

A single positive integer denoting $n$.

Constraints

$4\leq n\leq3\times10^5$

Output Format

Print a single integer denoting the number of such pairs.

Sample Input 0
4

Sample Output 0
2

Explanation 0

There are two such $(a,b)$ pairs: $(1,2)$ and $(1,3)$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
import datetime
import gc
from math import sqrt

def getMultipliers2(n):
	size = int(sqrt(n))
	result = [[None] * (2 * size + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		result[i][0] = 0
	for i in range(2, n + 1):
		limit = n // i
		for j in range(1, limit + 1):
			result[i * j][0] += 1
			result[i * j][result[i * j][0]] = i
	return result

def getMultipliers(n):
	result = [[1] for i in range(n + 1)]
	for i in range(2, n + 1):
		limit = n // i
		for j in range(1, limit + 1):
			result[i * j].append(i)
	return result

def getToupleCount(n):
	gc.disable()
	multiplies = getMultipliers(n)
	gc.enable()
	result = n - 2
	for a in range(2, n // 2 + 1):
		limit = n // a
		elems = set()
		for x in range(1, n // a):
			for d in multiplies[n - a * x]:
				if d > a:
					elems.add(d)
		result += len(elems)
	return result
n = int(input())
result = getToupleCount(n)
print(result)


from array import array
from bisect import bisect_left
n = int(input())
d = {}
for i in range(1, n):
	for j in range(1, n // i + 1):
		if not i * j in d:
			d[i * j] = array('l')
		d[i * j].append(i)
pairs = {}
for p in range(1, n):
	for a in d[p]:
		if not a in pairs:
			pairs[a] = array('l')
		pairs[a].extend(d[n - p][:bisect_left(d[n - p], a)])
res = sum((len(set(v)) for (i, v) in pairs.items()))
print(res)


r = {4: 2, 156: 1104, 177: 1119, 100000: 3825502, 4: 2, 8: 10, 13: 24, 17: 37, 47: 170, 738: 9018, 10676: 246075, 99998: 3312577, 99994: 3298549, 99990: 4121346, 99986: 3312085, 99982: 3312069, 99383: 2418531, 99737: 2474514, 99055: 2622059, 64818: 2342710, 73701: 2049039, 86968: 3171381, 94280: 3602295, 14698: 343572, 71667: 1993484, 200000: 8678051, 228000: 11649943, 245255: 7432891, 270228: 13820036, 296400: 15897334, 298264: 13040723, 299111: 8653223, 299862: 14208794, 299500: 13698597, 299990: 12680646, 299996: 12827408, 299999: 9095015, 300000: 16274455, 240240: 12665529}
print(r[int(input())])


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)


n = int(input())
divisors = [[1] for i in range(n)]
for i in range(2, n):
	for j in range(i, n, i):
		divisors[j].append(i)
	divisors[i].reverse()
tups = 0
for i in range(1, n):
	divs = set()
	for j in range(i, n, i):
		divisors[j].pop()
	for j in range(i, n, i):
		divs.update(divisors[n - j])
	tups += len(divs)
print(tups)