Задача 76224
|
|
 |
Условие
Дано натуральное n. Подсчитать количество решений
неравенства
x2 + y2 < n в натуральных
(неотрицательных целых) числах, не используя действий
с вещественными числами.
Решение
k := 0; s := 0;
{инвариант: s = количество решений неравенства
x*x + y*y < n c x < k}
while k*k < n do begin
| ...
| {t = число решений неравенства k*k + y*y < n
| с y>=0 (при данном k) }
| k := k + 1;
| s := s + t;
end;
{k*k >= n, поэтому s = количество всех решений
неравенства}
Здесь ... — пока ещё не написанный кусок программы,
который будет таким:
l := 0; t := 0;
{инвариант: t = число решений
неравенства k*k + y*y < n c 0<=y<l }
while k*k + l*l < n do begin
| l := l + 1;
| t := t + 1;
end;
{k*k + l*l >= n, поэтому t = число
всех решений неравенства k*k + y*y < n}
