Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

For positive integers $a$ and $b$, we say that a fraction $\frac{a}{b}$ is *good* if it is equal to $\frac{m}{m+1}$ for some positive integer $m$.

You are given an integer $N$. Find the number of pairs of integers $i, j$ such that $1 ≤ i, j ≤ N$ and the fraction $\frac{i}{i+1} \cdot \frac{j+1}{j}$ is good.

------  Input ------
The first and only line of the input contains a single integer $N$.

------  Output ------
Print a single line containing one integer ― the number of pairs of integers $i, j$ ($1 ≤ i, j ≤ N$) such that $\frac{i}{i + 1} \cdot \frac{j+1}{j}$ is good.

------  Constraints ------
$1 ≤ N ≤ 1,000,000$

------  Subtasks ------
Subtask #1 (5 points): $1 ≤ N ≤ 2,000$

Subtask #2 (10 points): $1 ≤ N ≤ 100,000$

Subtask #3 (85 points): original constraints

----- Sample Input 1 ------ 
5
----- Sample Output 1 ------ 
8
----- explanation 1 ------ 
The following eight pairs $(i, j)$ give good fractions: $(1,2)$, $(1,3)$, $(2,3)$, $(2,4)$, $(2,5)$, $(3,4)$, $(3,5)$ and $(4,5)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
import math
import sys
import random
import array as arr
import numpy as np
from sys import stdin, stdout
from collections import OrderedDict
from collections import defaultdict
from collections import deque
import heapq as hq

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

def single_input():
	return int(input())

def simple_input():
	return input()

def solve():
	n = int(stdin.readline())
	arr = [0] * (n + 2)
	for i in range(1, n + 2):
		j = i
		while j < n + 2:
			arr[j] += 1
			j += i
	ans = 0
	for i in range(1, n + 1):
		ans += arr[i] * arr[i + 1] / 2 - 1
	print(int(ans))

def main():
	t = 1
	for i in range(t):
		solve()
main()


max = int(1000000.0) + 7
arr = [0] * max
for i in range(1, max):
	for j in range(i, max, i):
		arr[j] += 1
n = int(input())
ans = 0
for i in range(1, n + 1):
	ans += arr[i] * arr[i + 1] // 2 - 1
print(ans)


maxSize = int(1000000.0) + 7
d = [0] * maxSize
for i in range(1, maxSize):
	for j in range(i, maxSize, i):
		d[j] += 1
N = int(input())
res = 0
for i in range(1, N + 1):
	res += d[i] * d[i + 1] // 2 - 1
print(res)


N = int(1000000.0) + 7
d = [0] * N
for i in range(1, N):
	for j in range(i, N, i):
		d[j] += 1
n = int(input())
ans = 0
for i in range(1, n + 1):
	ans += d[i] * d[i + 1] // 2 - 1
print(ans)


import sys, collections, math, itertools, random
INF = sys.maxsize

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

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

def input():
	return sys.stdin.readline().strip()
mod = 1000000007
n = int(input())
d = [0] * (n + 2)
for r in range(1, n + 2):
	for s in range(r, n + 2, r):
		d[s] += 1
ans = 0
for i in range(1, n + 1):
	ans += d[i] * d[i + 1] // 2 - 1
print(ans)