8747. Делимость суммы

Для заданного натурального значения k найдите наименьшее натуральное число n, при котором сумма 1 + 2 + 3 + ... + n делится на k.

Вход. Одно натуральное число k (k ≤ 10⁸).

Выход. Выведите искомое наименьшее натуральное число n.

Пример входа 1	Пример выхода 1
10	4
Пример входа 2	Пример выхода 2
11	10

РЕШЕНИЕ

циклы

Анализ алгоритма

Будем вычислять частичные суммы: 1, 1 + 2, 1 + 2 + 3, … до тех пор пока не найдется такое n, что 1 + 2 + 3 + ... + n делится на k.

Пример

Рассмотрим первый пример, в котором k = 10. Построим частичные суммы.

При n = 4 сумма равна 1 + 2 + 3 + 4 = 10 и делится на k = 10.

Реализация алгоритма

Читаем входное значение k.

scanf("%lld", &k);

В переменной s вычисляем частичные суммы. Изначально присвоим s = 0.

s = 0;

Перебираем значения n = 1, 2, … .

for (n = 1; ; n++)

{

s = s + n;

На данный момент s = 1 + 2 + 3 + ... + n. Если сумма делится на k, то ответом будет значение n.

if (s % k == 0) break;

}

Выводим ответ.

printf("%lld\n", n);