Контест Junior Сложность спрашивают часто обновлено
Число и сумма делителей до 10¹²
Условие
Дано натуральное число n. Найдите, сколько у него делителей и чему равна их сумма (включая 1 и само n).
Ввод: одно число n (1 ≤ n ≤ 10¹²).
Вывод: два числа через пробел: количество делителей и их сумма. Сумма может не поместиться в 32 бита.
Ограничение по времени 2 секунды: перебор всех чисел от 1 до n не уложится.
Пример 1
Ввод:
12
Вывод:
6 28
Пример 2
Ввод:
1
Вывод:
1 1
Как подойти
Подсказки: 2
- Делители идут парами d и n/d.
- Достаточно перебрать d до √n, сравнивая d·d ≤ n в целых числах.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.