1. Идея

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

Наивный способ — перебрать все числа от 1 до n - 1 и проверить, делят ли они n. Но при n до 10^12 так делать нельзя.

Главная идея — перебирать делители не до n, а только до sqrt(n). Если d делит n, то вместе с ним сразу находится парный делитель n / d.

Например, если n = 28, то:

• 2 — делитель, парный к нему 14
• 4 — делитель, парный к нему 7

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

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

1. У любого делителя d, меньшего корня из n, есть парный делитель n / d, больший корня из n.

2. Поэтому достаточно проверить все d от 2 до тех пор, пока d * d <= n.

3. Делитель 1 всегда является истинным делителем любого числа, кроме случая n = 1.

   • Для n = 1 истинных делителей вообще нет, их сумма равна 0, значит ответ NO.
   • Для всех n > 1 можно сразу начать сумму с 1.

4. Если d * d == n, то делитель встречается в паре сам с собой.

   • Например, у 36 делитель 6 парный сам себе.
   • В таком случае его нужно прибавить только один раз.

3. Алгоритм

1. Считать n.
2. Если n == 1, вывести NO.
3. Иначе завести сумму sum = 1, потому что 1 — истинный делитель любого числа больше 1.
4. Перебирать d от 2, пока d * d <= n:
   • если n % d == 0, то:
     • прибавить d к сумме;
     • найти other = n / d;
     • если other != d, тоже прибавить other.
5. После перебора сравнить sum и n:
   • если sum == n, вывести YES;
   • иначе вывести NO.

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

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

Для числа n > 1:

• делитель 1 мы добавляем сразу;
• дальше рассматриваем все числа d от 2 до sqrt(n).

Если d делит n, то существует парный делитель other = n / d. Тогда:

• d — делитель числа n;
• other — тоже делитель числа n.

Все делители числа, кроме 1 и самого n, обязательно попадут в одну из таких пар:

• либо как маленький делитель d <= sqrt(n),
• либо как большой делитель n / d.

Значит, перебирая все d до корня, мы находим все делители.

Почему не возникает пропусков:

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

Почему не возникает лишних добавлений:

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

Таким образом, сумма получается ровно суммой всех истинных делителей числа n. После этого остаётся только проверить, равна ли она самому числу.

5. Сложность

Перебор идёт только до sqrt(n).

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

При n <= 10^12 это подходит: максимум около 10^6 проверок.

6. Код на C++17

#include <iostream>
using namespace std;

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

    if (n == 1) {
        cout << "NO\n";
        return 0;
    }

    long long sum = 1;

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

    if (sum == n) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

n = int(input())

if n == 1:
    print("NO")
else:
    s = 1
    d = 2
    while d * d <= n:
        if n % d == 0:
            s += d
            other = n // d
            if other != d:
                s += other
        d += 1

    if s == n:
        print("YES")
    else:
        print("NO")