ЕГЭ–2026, информатика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 16 № 55603 Добавить в вариант

Алгоритм вычисления значения функции F(a, b), где a и b  — целые неотрицательные числа, задан следующими соотношениями:

F(a, 0)  =  a;

F(a, b)  =  F(a−b, b), если a ≥ b > 0;

F(a, b)  =  F(b, a), если a < b.

Укажите количество таких чисел n из интервала

123 456 795 ≤ n ≤ 1 234 567 888,

для которых F(n, 14)  =  1.

Спрятать решение

Решение.

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

Приведем решение на языке Python.

a_2 = len(range(123456796, 1234567889, 2))

a_7 = len(range(123456802, 1234567889, 7))

a_14 = len(range(123456802, 1234567889, 14))

print(len(range(123456795, 1234567888)) - a_2 - a_7 + a_14)

Ответ: 476190468.

Приведем решение Михаила Глинского на языке Python.

count = 0

for n in range(123456795, 1234567889,2):

if n%7 != 0:

count += 1

print(count)

Примечание: способ использует прямой перебор, что не очень рационально.

Аналоги к заданию № 55603: 55633 Все

Спрятать решение · Помощь