Даны натуральные числа а и b, причем b>0.  Найти частное  и  остаток  при  делении а на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением  деления  на  2  четных  чисел;  число  шагов  не должно превосходить C1*log(a/b) + C2 для некоторых констант C1, C2.

Решение.

  b1 := b;
  while b1 <= a do begin
  | b1 := b1 * 2;
  end;
  {b1 > a, b1 = b * (некоторая степень 2)}
  q:=0; r:=a;
  {инвариант: q, r - частное и остаток при делении a на b1,
   b1 = b * (некоторая степень 2)}
  while b1 <> b do begin
  | b1 := b1 div 2 ; q := q * 2;
  | { a = b1 * q + r, 0 <= r, r < 2 * b1}
  | if r >= b1 then begin
  | | r := r - b1;
  | | q := q + 1;
  | end;
  end;
  {q, r - частное и остаток при делении a на b}

---