eolymp
bolt
Try our new interface for solving problems
Məsələlər

Степан и пары

Степан и пары

Степана заинтересовал наибольший общий делитель пары чисел, а именно $НОД(x, y)$. По целому числу $n$ Степан хочет узнать, сколько существует таких пар целых чисел $(i, j)$, что $1 \le i, j \le n$ и выполняется равенство $i = GCD(i, j)$. \InputFile Одно целое число $n\:(1 \le n ≤ 10^6)$. \OutputFile Выведите количество искомых пар целых чисел.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
1
Çıxış verilənləri #1
1
Giriş verilənləri #2
4
Çıxış verilənləri #2
8
Giriş verilənləri #3
10
Çıxış verilənləri #3
27

Şərh: В первом примере подходящей парой есть пара (1, 1), так как НОД(1, 1) = 1. Во втором примере подходят 8 пар чисел: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).

Mənbə III этап Всеукраинской олимпиады школьников 2012-2013, 1 тур