Степан і пари#4283

Степан і пари (Розбір)

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

Кількість таких $i$ , для яких $i = НСД (i, j)$ i = НСД(i, j), дорівнює кількості дільників $d (j)$ числа $j$ . Оскільки $1 \leq j \leq n$ 1 \le j \le n, то залишається знайти кількість усіх дільників чисел від $1$ до $n$ . Тобто слід знайти суму

d (1) + d (2) + ... + d (n)

d(1) + d(2) + ... + d(n)

Оскільки обчислення $d (n)$ вимагає факторизації числа $n$ , то безпосереднє обчислення вказаної суми потребуватиме часу $O (n)$ .

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

i = 1 \sum n ⌊ \frac{n}{i} ⌋

\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor

Вказану суму можна знайти за час $O (n)$ .

Приклад

При $n = 6$ n = 6 маємо наступні пари:

Кількість пар дорівнює

6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 = = 6 + 3 + 2 + 1 + 1 + 1 = 14

6 / 1 + 6 / 2 + 6 / 3 + 6 / 4 + 6 / 5 + 6 / 6 = \\ = 6 + 3 + 2 + 1 + 1 + 1 = 14

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

Читаємо значення $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();
  }
}

Java

Python реалізація

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

n = int(input())

Обчислюємо відповідь за формулою і виводимо її.

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