Вариант 10. Дискретное извлечение корня Дискретным корнем из натурального числа n по модулю m называется такое наименьшее натуральное число k, что k
2
≡ n (mod m), то
есть такое, что число (k
2
– n) делится на m без остатка. Программа
должна извлекать дискретный корень из заданного натурального
числа по заданному простому модулю, если это возможно.
Входные данные. Целое положительное число n и простое число m.
Выходные данные. Дискретный корень из n по модулю m, либо
сообщение о том, что его не существует.
Пример текстового интерфейса пользователя
Discrete Square Root
Input a positive integer>13
Input a modulo>17
Result: 8
Continue? (Y/N)>Y
Input a positive integer>3
Input a modulo>11
Result: 5
Continue? (Y/N)>N

Описание алгоритма:
Будем наращивать длину последовательности от 0 знаков до N. Пусть после какого-то количества шагов у нас выписаны все последовательности длины А и мы хотим узнать количество подходящих последовательностей длины А+1. Распределим все последовательности на три группы(так как предыдущие символы нас не волнуют, то любые последовательности одной группы для нас равнозначны):
1) Заканчиваются на 0.
2) Ровно на одну единицу
3) Ровно на две единицы.
Из каждой последовательности группы 1 приписыванием нуля или единицы мы можем получить одну последовательность группы 1 и одну - группы 2. Неважно, какие именно, но они не перекрываются, т.к. предыдущие символы различны, хоть мы их и не учитываем. Точно так же из второй группы мы получаем одну последовательность группы 3 и одну группы 1, а из группы 3 - только группу 1. Таким образом, если количества последовательностей длины А по группам были (x, y, z), то для длины А+1 такое распределение будет (x+y+z, x, y). Если взять для длины 0 тройку (0, 0, 1) и просчитать тройки от 1 до N, получится искомое количество. Для N=1 и N=2 также работает правильно.
Программа на Pascal:

var num00,num01,num11,mem00:integer;
    n,i:byte;
begin
readln(n);
  num00:=1;
  for i:=1 to n do begin
    mem00:=num11;
    num11:=num01;
    num01:=num00;
    num00:=num01+num11+mem00;
  end;
writeln(num11+num01+num00);
end.

Program a4;
var
  x, kl, k2: integer;
begin
  kl := 0;
  k2 := 0;
  x:=1;
  while x<>0 do
  begin
    writeln ('Введите целое число');
    readln (x);
    if x<0 then kl := kl + 1;
    if x<0 then k2 := k2 + 1
  end;
  writeln ('kl=', kl, ' ', 'k2=', k2)
end.

Программа была написана с синтаксическими ошибками: a4 и х были записаны русскими буквами, а вместо нулей 0 использовалась буква О.
Кроме того, конструкции if x<0 then kl := kl + 1; и if x<0 then k2 := k2 + 1 делают одно и то же, только с разными переменными. Скорее всего, одно из условий должно содержать знак не меньше, а больше, либо больше или равно.