Разбор

Зафиксируем $j$ (например $j=12$) и найдем количество таких $i$, что $i=НОД(i,12)$. Найдем значения $i$, удовлетворяющие этому равенству. Ими будут $i=1,2,3,4,6,12$. То есть любое $i$, являющееся делителем $12$, удовлетворяет равенству $i=НОД(i,12)$.

Количество таких $i$ для которых $i=НОД(i,j)$, равно количеству делителей $d(j)$ числа $j$. Поскольку $1\le j\le n$, то остается найти количество всех делителей чисел от $1$ до $n$. То есть следует найти сумму $d(1)+d(2)+...+d(n)$. Поскольку вычисление $d(n)$ требует факторизации числа $n$, то непосредственное вычисление указанной суммы потребует времени $O(n)$.

Посмотрим на сумму делителей по-другому. Среди делителей чисел от $1$ до $n$ единица будет встречаться $\lfloor \frac{n}{1}\rfloor$ раз, двойка $\lfloor \frac{n}{2}\rfloor$ раз и так далее (делитель $i$ будет встречаться $\lfloor \frac{n}{i}\rfloor$ раз). Количество искомых пар целых чисел равно

Указанную сумму можно найти за время $O(n)$.

Пример

При $n=6$ имеем следующие пары:

Количество пар равно

Реализация алгоритма

Читаем значение $n$.

scanf("%d",&n);

Вычисляем ответ по формуле и выводим его.

s = 0;
for(i = 1; i <= n; i++)
  s += n / i;
printf("%d\n",s);

Java реализация

import java.util.*;

class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int s = 0;
    for(int i = 1; i <= n; i++)
      s += n / i;
    System.out.println(s);
    con.close();
  }
}

Python реализация

Читаем значение $n$.

n = int(input())

Вычисляем ответ по формуле и выводим его.

s = 0
for i in range(1,n+1):
  s += n // i
print(s)