1. Идея

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

Самый прямой способ:

• перебрать все числа x от 1 до n;
• для каждого числа посчитать количество его делителей;
• запомнить число с наибольшим количеством делителей.

Так как n <= 10^5, такой перебор успевает.

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

1. Как считать делители числа

Если d делит x, то вместе с ним делителем является и x / d.

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

• 1 и 12
• 2 и 6
• 3 и 4

Поэтому не нужно проверять все числа от 1 до x. Достаточно проверить только d от 1 до тех пор, пока d * d <= x.

Если нашли делитель d, то:

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

Например, для x = 9:

• 1 даёт пару 1 и 9
• 3 даёт пару 3 и 3, но это один делитель, а не два

2. Если ответов несколько

По условию можно вывести любое подходящее число.

В эталонном решении ответ обновляется только если найдено строго больше делителей: if cnt > best_divs

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

Это полностью подходит под условие.

3. Алгоритм

1. Считать n.
2. Завести:
   • best_num = 1 — текущее лучшее число;
   • best_divs = 1 — количество его делителей.
3. Для каждого x от 1 до n:
   1. Посчитать число его делителей:
      • cnt = 0
      • перебирать d от 1, пока d * d <= x
      • если x % d == 0, то:
        • прибавить 2
        • если d * d == x, вычесть 1
   2. Если cnt > best_divs, обновить:
      • best_divs = cnt
      • best_num = x
4. Вывести best_num.

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

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

Подсчёт делителей для одного числа

Для фиксированного числа x мы перебираем все d от 1 до sqrt(x).

• Если d не делит x, ничего не происходит.
• Если d делит x, то существует парный делитель x / d.
• Значит, каждый найденный делитель d даёт либо:
  • два разных делителя: d и x / d,
  • либо один делитель, если d * d == x.

Так мы учитываем все натуральные делители числа x и не пропускаем ни одного.

Поиск лучшего числа

Алгоритм проверяет каждое число от 1 до n и для каждого точно знает число его делителей.

Затем он хранит число с максимальным найденным значением.

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

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

5. Сложность

Для каждого x от 1 до n перебираются делители до sqrt(x).

Итоговая сложность:

• по времени: O(n * sqrt(n))
• по памяти: O(1)

Для n <= 10^5 этого достаточно.

6. Код на C++17

#include <iostream>
using namespace std;

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

    int best_num = 1;
    int best_divs = 1;

    for (int x = 1; x <= n; x++) {
        int cnt = 0;
        for (int d = 1; 1LL * d * d <= x; d++) {
            if (x % d == 0) {
                cnt += 2;
                if (d * d == x) {
                    cnt--;
                }
            }
        }
        if (cnt > best_divs) {
            best_divs = cnt;
            best_num = x;
        }
    }

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

7. Код на Python 3

n = int(input())

best_num = 1
best_divs = 1

for x in range(1, n + 1):
    cnt = 0
    d = 1
    while d * d <= x:
        if x % d == 0:
            cnt += 2
            if d * d == x:
                cnt -= 1
        d += 1
    if cnt > best_divs:
        best_divs = cnt
        best_num = x

print(best_num)