function СуммаКвадратовЦифр(Число: integer): integer;
begin
Result := 0;
while Число > 0 do
begin
Result += Sqr(Число mod 10);
Число := Число div 10
end
end;
function ЧислоПервоклассное(Число: integer): boolean;
begin
Число := Abs(Число); // защита от злобных буратинок
var L:=new SortedSet<integer>;
L.Add(Число);
repeat
case Число of
0, 2, 3:
begin
Result := False;
Exit
end;
1:
begin
Result := True;
Exit
end;
else
begin
Число := СуммаКвадратовЦифр(Число);
if L.Contains(Число) then
begin
Result:=False;
Exit
end
else L.Add(Число)
end
end
until False // бесконечный цикл
end;
begin
var (НижняяГраница, ВерхняяГраница) := ReadInteger2;
var Количество := 0;
for var ОчередноеЧисло := НижняяГраница to ВерхняяГраница do
if ЧислоПервоклассное(ОчередноеЧисло) then Inc(Количество);
Количество.Println
end.
1 10020Он получил произведение исходных чисел.
За странным описанием процесса по сути скрывается описание алгоритма умножения в столбик двоичных чисел: на i-м шаге, если первое число нечетное (=если на i-м месте справа в первом числе стоит 1), к сумме прибавляется 2^(i - 1) * второе число (=если всё записано в двоичной системе счисления, умножение на степень двойки равносильно сдвигу числа влево).
Инвариант тут такой: в любой момент времени сумма всех чисел, записанных на доске, и произведения чисел, записанных на карточке, не меняется.
Сначала на примере, если на карточке записаны 5 и 7:
карточка: 5 и 7, сумма на доске: 0карточка: 2 и 14, сумма на доске: 7карточка: 1 и 28, сумма на доске: 7карточка: 0 и 56, сумма на доске: 7 + 28 = 35В общем случае: пусть перед текущим шагом на доске числа a и b, сумма чисел на доске s; значение суммы ab + s. Есть два случая:
a = 2a'. Тогда на следующем шаге на карточке будет a' и 2b, на доске ничего не изменится. Значение суммы a' * 2b + s = 2a' * b + s = ab + sa = 2a' + 1. На следующем шаге на карточке a' и 2b, на доску добавится b. Значение суммы a' * 2b + s + b = (2a' + 1) b + s = ab + sИзначально на доске выписаны числа суммой 0 (инвариант равен произведению чисел на карточке = p), в конце произведение чисел на карточке равно 0, тогда сумма выписанных чисел равна p.
