1. Идея

Нужно найти сумму всех натуральных делителей числа n.

Перебирать все числа от 1 до n и проверять, делят ли они n, слишком долго: при n до 10^12 такой способ не подойдет.

Ключевая идея — делители удобно искать парами.

Если i делит n, то вместе с ним существует парный делитель n / i.

Например, у числа 36:

• 1 и 36
• 2 и 18
• 3 и 12
• 4 и 9
• 6 и 6

Поэтому достаточно перебирать только числа от 1 до sqrt(n). Для каждого найденного делителя:

• добавляем i,
• добавляем n / i,
• но если это одно и то же число, второй раз добавлять не нужно.

2. Наблюдения

Наблюдение 1. Делители идут парами

Если i — делитель числа n, то n = i * (n / i), значит n / i тоже делитель.

Это позволяет за одну проверку находить сразу два делителя.

Наблюдение 2. Достаточно проверять до корня

Если i > sqrt(n) и i делит n, то парный делитель n / i уже будет меньше sqrt(n).

Значит, все пары делителей будут найдены, если перебрать только i, для которых i * i <= n.

Наблюдение 3. Квадрат числа — особый случай

Если n — точный квадрат, то для i = sqrt(n) парный делитель совпадает с самим i.

Например, у 36 это 6, потому что 36 / 6 = 6.

В таком случае нужно добавить это число только один раз.

3. Алгоритм

1. Считать число n.
2. Завести переменную sum = 0.
3. Перебирать i от 1, пока i * i <= n.
4. Если n % i == 0, то:
   • прибавить к ответу i,
   • вычислить other = n / i,
   • если other != i, прибавить и other.
5. Вывести sum.

4. Почему это работает

Докажем, что алгоритм находит сумму всех натуральных делителей числа n.

Рассмотрим любой натуральный делитель d числа n.

Тогда существует парный делитель n / d. Из двух чисел d и n / d хотя бы одно не больше sqrt(n). Значит, при переборе i от 1 до sqrt(n) мы обязательно встретим один элемент этой пары.

Когда это произойдет:

• если i делит n, алгоритм добавит i,
• и сразу добавит парный делитель n / i.

Таким образом, каждая пара делителей учитывается полностью.

При этом:

• ни один делитель не пропускается,
• ни один делитель не добавляется дважды,
• кроме случая i = n / i, то есть когда i * i = n; этот случай отдельно обработан проверкой other != i.

Следовательно, алгоритм суммирует все натуральные делители числа n ровно по одному разу, значит ответ будет правильным.

5. Сложность

Перебор идет до sqrt(n).

• Время: O(sqrt(n))
• Память: O(1)

При n <= 10^12 это достаточно быстро.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    long long sum = 0;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            long long other = n / i;
            if (other != i) {
                sum += other;
            }
        }
    }

    cout << sum << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())

s = 0
i = 1
while i * i <= n:
    if n % i == 0:
        s += i
        other = n // i
        if other != i:
            s += other
    i += 1

print(s)