алгоритмы - Нарисовать окружность

Достаточно найти все решения уравнения $%a^2+b^2=R$% в целых неотрицательных числах. Можно также положить $%a\le b$%, но это не даст экономии, если все решения потом всё равно надо будет выписать.

Зная все пары вида $%(a,b)$%, мы добавляем к ним симметричные пары вида $%\pm a,\pm b)$% (для любого набора знаков), и прибавляем их к $%(x_0,y_0)$%. Это даёт все значения для $%(x,y)$%.

Можно также заметить, что для $%R$% вида $%4k+3$% множество решений будет пусто, так как квадрат целого числа при делении на 4 даёт в остатке 0 или 1. Кроме того, если $%R$% делится на 4, то оба числа $%a$%, $%b$% должны быть чётными. Тогда задача сводится к поиску решений для $%R/4$% вместо $%R$%. Так мы делим на 4 столько раз, сколько возможно, и полученное новое число снова проверяем на предмет представления в виде $%4k+3$%. Скажем, если было $%R=112$%, то после двух делений на 4 получится значение 7, и в этом случае решений нет.

Таким образом, всё сводится к случаю, когда $%R$% даёт остаток 1 или 2 от деления на 4. Здесь можно составить массив из точных квадратов: 0, 1, 4, ... , $%n^2$%, где $%(n+1)^2 > R$%. Далее сравниваем этот массив с другим упорядоченным по возрастанию массивом $%R-n^2$%, ... , $%R-1$%, $%R$%, и при чтении обоих массивов один раз отыскиваем общие элементы. Если $%i$%-й элемент первого массива совпал с $%j$%-м элементом второго, то мы получили решение $%(a,b)=(i,n+1-j)$% (номера элементов в процессе чтения запоминаем, чтобы специально не искать).