Задание 16. Информатика. ЕГЭ. Поляков-6072

Функция \(F(n)\) может быть преобразована следующим образом: $$F(n) = F(n-1) + 2 \cdot n = F(n-2) + 2 \cdot (n - 1) + 2 \cdot n = \ldots = 2 \cdot 1 + 2 \cdot 2 + \ldots + 2 \cdot (n - 1) + 2 \cdot n = $$ $$= 2 \cdot (1 + 2 + \ldots + (n - 1) + n) = 2 \cdot S(n)$$ Здесь \(S(n)\) — сумма натуральных чисел от \(1\) до \(n.\) Очевидно, что \(F(n)\) делится на \(3,\) тогда и только тогда, когда \(S(n)\) делится на \(3.\) Рассмотрим первые три натуральных чисел. Для остальных чисел результат будет повторяться с периодом \(3.\)

\(n\)	\(1\)	\(2\)	\(3\)
\(S(n)\)	\(1\)	\(3\)	\(6\)
\(S(n) \, \% \, 3\)	\(1\)	\(0\)	\(0\)

Видно, что \(S(n)\) не делится на \(3,\) если остаток деления \(n\) на \(3\) равен \(1.\)

Получаем, что $$100~000~000 \, \% \, 3 = 1$$ Это число удовлетворяет условию задачи. Два следующих числа не походят. Далее $$200~000~000 \, \% \, 3 = 2$$ Это число не удовлетворяет условию задачи. Предыдущее походит. Разобьём отрезок от \(100~000~000\) до \(199~999~998\) на тройки. Из каждой тройки только для первого числа \(F(n)\) не делится на \(3.\) Не забудем также, что нам подходит число \(199~999~999.\) Окончательно, находим ответ:

Python

print(1 + (199_999_998 - 99_999_999) // 3)

Ответ: \(33333334\)