Отправлено: 21.01.20 20:06. Заголовок: егэ 21 № 87

Здравствуйте,у меня f(20,4) получается f(16,4)=(12,4)=(8,4)=(4,4)=4, тогда k=0
Значит мне нужно посчитать на промежутке от 1 до 100 количество чисел , в которых при вычитании 4 не дадут 2?

87) (Д. Муфаззалов, Белград). Напишите в ответе количество различных значений входной переменной a из интервала от 1 до 100 (включая границы), при которых программа выдаёт тот же ответ, что и при входном значении a = 20. Значение a = 20 также включается в подсчёт различных значений a.
var i, k, a: integer;
function f(x: integer; y: integer): integer;
begin
if x = y then
f := x else
if x > y then f := f(x - y, y)
else f := f(x, y - x);
end;
begin
k := 0;
readln(a);
for i := 1 to a do
if f(i, 4) = 2 then k := k + 1;
writeln(k);
end.

 Отправлено: 22.01.20 01:14. Заголовок: Ответ

Здравствуйте, GAF!

цитата:

function f(x: integer; y: integer): integer; begin if x = y then f := x else if x > y then f := f(x - y, y) else f := f(x, y - x); end;

1) Функция f(x,y) по алгоритму Евклида вычисляет наибольший общий делитель (НОД) чисел x и у, то есть f(x,y) = НОД(x,y).

2) f(i,4) = 2 --> НОД(i,4) = 2

3) Поскольку НОД(x,y) равен произведению одинаковых простых множителей x и y, то из НОД(i,4) = 2 следует, что в число простых множителей i может входить только одна 2, а произведение других простых множителей i даст числа 1, 3, 5, 7, 9, 11, 13, 15, ...

Соответственно, i будет равно 2, 6, 10, 14, 18, 22, 26, 30, ...

4) В цикле

цитата:

for i := 1 to a do if f(i, 4) = 2 then k := k + 1;

при a=20 условие выполнится для чисел 2, 6, 10, 14, 18 и k станет равно 5 (k = 5).

5) Такой же результат будет получен при a = 18, 19, 20, 21 (k = 5, i = 2, 6, 10, 14, 18).
(При a > 21 будет k > 5).

Ответ: 4 (четыре числа a = 18, 19, 20, 21).