Задача: х*х+у*у=19451945
Написать код для 7.7 для нахожддения всех корней.

Ну х=0, y корень из 19451945?
Или наоборот

Целочисленные, или вообще?

так это ж уравнение окружности.

(3) верно, все точки не нужны, выбрать целочисленные.

(1) это для У=0? Не годится, должно быть два целых числа.

целочисленных - 5 пар.

(2) целочисленные.

Вот тебе прототип, поменяй условие в функции. Что-то для онлайн-олимпиады школьник делал.

//*******************************************
Процедура Сформировать()
    
Для X = 1 По Лимит Цикл
   Для Y = 1 По Лимит Цикл
      Рез = ПосчитатьВариант(X, Y);
         Если Рез = 0 Тогда
       Сч = СчЧ + 1;
           Сообщить(X,Y);
      КонецЕсли;
   КонецЦикла;
КонецЦикла;
Сообщить("Решений " + Сч);
КонецПроцедуры

(6) Нет.
x=256 y=4403

x=344 y=4397

x=581 y=4372

x=1252 y=4229

x=2363 y=3724

x=2437 y=3676

x=2632 y=3539

x=3088 y=3149

x=3149 y=3088

x=3539 y=2632

x=3676 y=2437

x=3724 y=2363

x=4229 y=1252

x=4372 y=581

x=4397 y=344

x=4403 y=256

тады 8. или 16 если зеркальные считать разными.

(8) это ж тупым перебором, так неинтересно

у мну на компе тупым перебором
1: 256,4403
2: 344,4397
3: 581,4372
4: 1252,4229
5: 2363,3724
6: 2437,3676
7: 2632,3539
8: 3088,3149
9: 3149,3088
10: 3539,2632
11: 3676,2437
12: 3724,2363
13: 4229,1252
14: 4372,581
15: 4397,344
16: 4403,256
Решений 16 за 23.635
.
дальше можно оптимизировать, в т.ч. и на контроль достижения зеркальности и далее вычислять не надо, просто взять найденное поменять в парах местами ;-)

(11) Перебор сработал быстро.

Процедура Сформировать()
    
    
Сч=0;    
Для X = 1 По 4410 Цикл
   Для Y = 1 По 4410 Цикл
      Рез = (X*X) + (Y*Y);
      Если Рез = 19451945 Тогда
           Сч = Сч + 1;
        Сообщить(Строка(X)+" и "+Строка(Y));
      КонецЕсли;
   КонецЦикла;
КонецЦикла;
Сообщить("Решений " + Сч);
КонецПроцедуры

Получил
256 и 4403
344 и 4397
581 и 4372
1252 и 4229
2363 и 3724
2437 и 3676
2632 и 3539
3088 и 3149
3149 и 3088
3539 и 2632
3676 и 2437
3724 и 2363
4229 и 1252
4372 и 581
4397 и 344
4403 и 256
Решений 16

(13) малость соптимизировать, отсекая уже пройденное

Время1 = _GetPerformanceCounter();
Лимит = 4411; Сч = 0;

//Для X = 1 По Лимит Цикл Состояние(""+X+" из "+Лимит); XX = X*X; Для Y = 1 По Лимит Цикл Рез = XX + Y*Y; Если Рез = 19451945 Тогда Сч = Сч + 1; Сообщить(""+сч+": "+X+","+Y); Прервать; КонецЕсли; КонецЦикла; КонецЦикла;
ПредыдущийИгрек = Лимит;
Флаг = 1;

Для X = 1 По Лимит Цикл
    XX = X*X;
    Для Y = -ПредыдущийИгрек По -1 Цикл
        Если Флаг = 1 Тогда Сообщить("начинаем с "+(-Y)); Флаг = 0; КонецЕсли;
        Рез = XX + Y*Y;
        Если Рез = 19451945 Тогда
            ПредыдущийИгрек = -Y;
            ПредыдущийИгрек = ПредыдущийИгрек-1;
            сч = сч + 1; Сообщить(""+сч+": "+X+","+(-Y));
            Флаг = 1;
            Прервать;
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

начинаем с 4411
1: 256,4403
начинаем с 4402
2: 344,4397
начинаем с 4396
3: 581,4372
начинаем с 4371
4: 1252,4229
начинаем с 4228
5: 2363,3724
начинаем с 3723
6: 2437,3676
начинаем с 3675
7: 2632,3539
начинаем с 3538
8: 3088,3149
начинаем с 3148
9: 3149,3088
начинаем с 3087
10: 3539,2632
начинаем с 2631
11: 3676,2437
начинаем с 2436
12: 3724,2363
начинаем с 2362
13: 4229,1252
начинаем с 1251
14: 4372,581
начинаем с 580
15: 4397,344
начинаем с 343
16: 4403,256
начинаем с 255
Решений 16 за 56.063 - если в одну строку то будет секунд 19

можно еще больше соптимизировать по колву вычисляемых значений в циклах

Вы что издеваетесь? В клюшках корней нет? Одного цикла достаточно

(18) не нема, ни sqr, ни sqrt

(19) и pow нет?

Exp?

(20) губу на лоб пришпили ;-)

(21) ...и пришей ;-)

циклы шагать надо не по 1, а с вычисляемым шагом

в (15) 16'017'767 итераций, сэкономлено почти 3.5млн итераций тупого перебора ;-)

(23) вот же извращенцы, логарифмы аж 3 штуки положили, а прямой операции не одной))
(25) да не нужно вложенных циклов. Все квадраты загнать в коллекцию, а потом в цикле поиск. Или поиск там тоже тупым перебором?

(26) Поиск чего?

(27) разницы в списке квадратов

зачем все обсчитывают четверть круга, если из соображений симметрии очевидно что надо считать осьмушку? дальше все зеркалится.

(29) опоздун, ранее об этом замечали уже

(8) 1 цикл + функция SQRT

(19) всё там есть. И штатно, и через класс Math

http://my1c-archive.narod.ru/knowhow.html#MATH

https://www.1cpp.ru/docum/html/Math.html

слабо запросом?

(32) штатно?

(36) смотри (33)

(37) это понятно, встроенных по языку нет

(35) Можно и запросом. На 1sqlite те же 16 вариантов - 2.8c


WITH RECURSIVE
cnt(x,x2) AS (
    SELECT 1,1
    UNION ALL
    SELECT x+1, (x+1)*(x+1)
    FROM cnt
    WHERE x2<19451945
)
SELECT
    cnt.x AS  x,
    cnt2.x as y,
    cnt.x2+cnt2.x2 AS z
FROM cnt
CROSS JOIN cnt AS  cnt2 ON (cnt.x2+cnt2.x2)==19451945


(18) :)
слабо написать?
sc=createObject("msScriptControl.scriptControl");
  sc.language="VBscript";

(40) а если под вайном?

(15) что у меня нифига не секунды считает...

тупо алгоритмом Брезенхема, с проверкой при изменении координат
тестил на снеговике, клюшек под рукой нет

&НаКлиенте
Процедура Команда1(Команда)
R = 4410; //19451945;
X1=0;
Y1=0;
x = 0;
y = R;
Начало=ТекущаяДата();
delta = (1 - 2 * R);
error = 0;
счРешений=0;  
пока (y >= 0) Цикл
    Если x>y  Тогда // считаем осьмушку
        Прервать;
    КонецЕсли;
       error = (2 * (delta + y) - 1);
       Если ((delta < 0) И (error <= 0)) Тогда
           Если x*x+y*y=19451945 Тогда
               счРешений = счРешений + 1;
               Сообщить("Решение №"+счРешений+" х="+(x)+ " y="+(y));  
           КонецЕсли;
           x = x + 1;
           delta = delta +  (2 * x + 1);
           Продолжить;
       КонецЕсли;
       error = 2 * (delta - x) - 1;
       Если ((delta > 0) И (error > 0)) Тогда
           Если x*x+y*y=19451945 Тогда
               счРешений = счРешений + 1;
               Сообщить("Решение №"+счРешений+" х="+(x)+ " y="+(y));  
           КонецЕсли;
           Y = Y - 1;
          
          delta = delta +  1 - 2 * y;
           Продолжить;
       КонецЕсли;
           Если x*x+y*y=19451945 Тогда
               счРешений = счРешений + 1;
               Сообщить("Решение №"+счРешений+" х="+(x)+ " y="+(y));  
           КонецЕсли;
       x = x + 1;
       delta = delta + 2 * (x - y);
       y = y - 1;
  КонецЦикла;
конец = ТекущаяДата();
Сообщить("решений:"+счРешений);
Сообщить("время="+(ТекущаяДата()-Начало));
//возврат;
// Злоп
Начало=ТекущаяДата();
Лимит = 4411;
Сч = 0;

//Для X = 1 По Лимит Цикл Состояние(""+X+" из "+Лимит); XX = X*X; Для Y = 1 По Лимит Цикл Рез = XX + Y*Y; Если Рез = 19451945 Тогда Сч = Сч + 1; Сообщить(""+сч+": "+X+","+Y); Прервать; КонецЕсли; КонецЦикла; КонецЦикла;

ПредыдущийИгрек = Лимит;
Флаг = 1;
счРешений=0;
Для X = 1 По Лимит Цикл
    XX = X*X;
    Для Y = -ПредыдущийИгрек По -1 Цикл
        Если Флаг = 1 Тогда Сообщить("начинаем с "+(-Y)); Флаг = 0; КонецЕсли;
        Рез = XX + Y*Y;
        Если Рез = 19451945 Тогда
            ПредыдущийИгрек = -Y;
            ПредыдущийИгрек = ПредыдущийИгрек-1;
               счРешений = счРешений + 1;
               Сообщить("Решение №"+счРешений+" х="+(X)+ " y="+(-Y));  
            Флаг = 1;
            Прервать;
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
Сообщить("решений:"+счРешений);
Сообщить("время="+(ТекущаяДата()-Начало));
КонецПроцедуры

Брезенхем - 1 секунда, код злопа - 930

Решение №1 х=256 y=4 403
Решение №2 х=344 y=4 397
Решение №3 х=581 y=4 372
Решение №4 х=1 252 y=4 229
Решение №5 х=2 363 y=3 724
Решение №6 х=2 437 y=3 676
Решение №7 х=2 632 y=3 539
Решение №8 х=3 088 y=3 149
решений:8
время=0
начинаем с 4 411
Решение №1 х=256 y=4 403
начинаем с 4 402
Решение №2 х=344 y=4 397
начинаем с 4 396
Решение №3 х=581 y=4 372
начинаем с 4 371
Решение №4 х=1 252 y=4 229
начинаем с 4 228
Решение №5 х=2 363 y=3 724
начинаем с 3 723
Решение №6 х=2 437 y=3 676
начинаем с 3 675
Решение №7 х=2 632 y=3 539
начинаем с 3 538
Решение №8 х=3 088 y=3 149
начинаем с 3 148
Решение №9 х=3 149 y=3 088
начинаем с 3 087
Решение №10 х=3 539 y=2 632
начинаем с 2 631
Решение №11 х=3 676 y=2 437
начинаем с 2 436
Решение №12 х=3 724 y=2 363
начинаем с 2 362
Решение №13 х=4 229 y=1 252
начинаем с 1 251
Решение №14 х=4 372 y=581
начинаем с 580
Решение №15 х=4 397 y=344
начинаем с 343
Решение №16 х=4 403 y=256
начинаем с 255
решений:16
время=930

(44) ты злопа в чем меряешь?
У меня он 53 секунды гдето

(45) в секундах, конечно. в попугаях ты длиннее...
единственное, что твой код считает четверть, мой - осьмушку. Ну, получится одна секунда против 465...
клюшек нет под рукой, гонял на снеговике на клиенте. прогони, по возможности, мой код на клюшках, плз.

(46) вечером прогоню
И что у тебя за комп? Целерон что ли, отчего злоп так долго считает?
У меня ноут что-то типа и5-6670hq

(46) хотя вру, для осьмушки он не вдвое сократится, а меньше - у тебя ж сокращается второй цикл... запустил на осьмушку, сейчас посчитает, скажу.
но меня как-то разница между твоими 53 секунды, и моими 930 напрягает

не, я на сервере РДПшном, в форме на клиенте

+(49) досчитает, сделаю НаСервере, проверю. но как-то  странно

(47) 733 секунды получилось

(51) что то не так в твоем королевстве, ща переползу на свой комп

(46) Ух ты, алгоритм Брезенхема это очень быстро!
91 ms Брезенхем, 63240 ms Злоп, 2867 ms 1sqlite
На sqlite такое видимо не сотворить, хранимок то нет...


Решение №1 х=256 y=4403
Решение №2 х=344 y=4397
Решение №3 х=581 y=4372
Решение №4 х=1252 y=4229
Решение №5 х=2363 y=3724
Решение №6 х=2437 y=3676
Решение №7 х=2632 y=3539
Решение №8 х=3088 y=3149
решений:8
время=91
начинаем с 4411
Решение №1 х=256 y=4403
начинаем с 4402
Решение №2 х=344 y=4397
начинаем с 4396
Решение №3 х=581 y=4372
начинаем с 4371
Решение №4 х=1252 y=4229
начинаем с 4228
Решение №5 х=2363 y=3724
начинаем с 3723
Решение №6 х=2437 y=3676
начинаем с 3675
Решение №7 х=2632 y=3539
начинаем с 3538
Решение №8 х=3088 y=3149
начинаем с 3148
Решение №9 х=3149 y=3088
начинаем с 3087
Решение №10 х=3539 y=2632
начинаем с 2631
Решение №11 х=3676 y=2437
начинаем с 2436
Решение №12 х=3724 y=2363
начинаем с 2362
Решение №13 х=4229 y=1252
начинаем с 1251
Решение №14 х=4372 y=581
начинаем с 580
Решение №15 х=4397 y=344
начинаем с 343
Решение №16 х=4403 y=256
начинаем с 255
решений:16
время=63240


(53) только вот какого хрена у меня метод злопа медленно так считает?

ха! На сервере - метод злопа 343

"алгоритм Брезенхема для рисования окружностей" это гениально конечно

вместо полного перебора рисуем (получаем массив пар x,y) точки осьмушки окружности
затем прогоняем их на равенство
ну и последним шагом зеркалируем

Задачку (0) можно смело на олимпиаду по информатике

(53) брезенхем - O(n), у злопа что-то типа O(n)O(log n). твой я что-то не оценю, на план смотреть надо.
(56) чую я, что есть подводные камни у брезенхема...

(54) восьмерочники должны страдать.
представляю как у тебя снеговик скрипит

(59) на сервере - на порядок быстрее

(58) >чую я, что есть подводные камни у брезенхема...
теоретически оно дает наиболее близкие целые точки к окружности
лишние могут быть и много! пропустить ничего не должно

(61) лишние мы отсекаем проверкой. а вот насчет пропусков - опасаюсь я там, где малое изменение..
эх, не хватает математических знаний...

(61)+ хмм да есть подвох
может пропустить точки

(62) да сча прикинул и может запросто пропустить
надо +- соседние точки проверять еще

(63) хотя как раз на первой части в данном случае пропусков не будет, будут в конце, если четверть считать.

злоп, ну что там? галактеко волнуеццо!

(65) везде может пропускать и в начале тоже, точнее зависит какая четверть и откуда-куда рисуем
в середине менее вероятно, с одного края более чем с другого
алгоритм шахматкой идет и по диагонали может не нарисовать

(67) лениво уже в пятницу вечером думать...

(57) По математике. У нее кажется есть красивое решение, вроде у Савватеева мелькало.
По информатике на какую олимпиаду, задача в лоб решается.

(58)
МАКИВАРА:
Решение №1 х=256 y=4403
Решение №2 х=344 y=4397
Решение №3 х=581 y=4372
Решение №4 х=1252 y=4229
Решение №5 х=2363 y=3724
Решение №6 х=2437 y=3676
Решение №7 х=2632 y=3539
Решение №8 х=3088 y=3149
Решений 8 за 0.063 сек, за 3'121 итераций

ЗЛОП (костылем искусственно отсек осьмушку)
начинаем с 4410
1: 256,4403
начинаем с 4402
2: 344,4397
начинаем с 4396
3: 581,4372
начинаем с 4371
4: 1252,4229
начинаем с 4228
5: 2363,3724
начинаем с 3723
6: 2437,3676
начинаем с 3675
7: 2632,3539
начинаем с 3538
8: 3088,3149
Решений 8 за 42.702 сек, за 12'762'411 итераций

(66) комп у тебя гавно, вот что ;-)

(70) ну, значит порядок цЫфер верный. Это радует
(71) видимо, тонкости работы клиента/сервера. Может, и комп говно.

(69) эээ нет даже полный перебор можно сократить правильно
можно взять четверть вместо круга
можно восьмую часть
а можно взять прямоугольник дуги восьмой части и без Брезенхема обойтись

(73) При наличии корней - задача банальная. При отсутствии - проще реализовать их расчет (хотя бы итерационно).

(74) банальная не значит оптимальное решение

(75)+ если вместо миллионов радиус сделать побольше то перебором будет договато

(72) какой клиент-сервер на клюшках? 430 вместо 43 - на порядок отличие

(75) оптимальное решение на поверхности и сложность его O(sqrt(N)).
Весь сыр-бор в теме только от отсутствия корней в клюшках.

(78) вычисление квадратного корня это не оптимальная штука

(79)+ Книга знаний: Математические вычисления в 1С
во всех ЯП оно достаточно накладно считается

(78) если есть решение с таким O(), то корень можно и методом ньютона сделать. Показывай.

(81) дык вероятно y через x выразить и пробежаться по x, вычисляя y и проверяя на целое

(82)+ только внутри O() будет не совсем оно ибо для вычисления корня нужны циклы

(81) Реально издеваетесь)))?

    N = 19451945;
    Для X = 1 По Цел(Sqrt(N)) Цикл
        Y = Цел(Sqrt(N-X*X));
        Если X*X + Y*Y = N Тогда
            Сообщить(""+X+"    "+Y);
        КонецЕсли;
    КонецЦикла;

(84) >Y = Цел(Sqrt(N-X*X));
вот тут у тебя скрытый цикл, пусть и небольшой

(85) Только общую сложность он не сильно меняет. Пусть будет O(Sqrt(N)*Log(N))

(86) O(n) получается. Как у брезенхема.

(87) с чего вдруг?

(84) можно только нечетные перебирать

А разве корень не вычисляется соответствующей командой ассемблера?

Если считать что факторизация правой части известна
5 * 73 * 137 * 389
То каждое из чисел можно представить образом в виде суммы квадратов
Далее комбинировать решения, используя, что если a=x^2+y^2 и b=z^2+t^2
тогда a*b=(xz+yt)^2+(xt-yz)^2=(xz-yt)^2+(xt+yz)^2
То есть каждый множитель даёт два варианта
Отсюда решений 2^4=16 если считая только положительные

(90) сомневаюсь

(92) есть конечно же
https://www.club155.ru/x86cmdfpu/FSQRT

(91) а вот и красота подъехала) А доказать что других решений нет?

(92) у современных процов уже сотни инструкций. Даже если корня нет, то лог и экспонента должны быть

(94) чето я уже слаб в этом
Можно почитать тут https://ru.m.wikipedia.org/wiki/Гауссовы_целые_числа#Подсчёт_числа_представлений_в_виде_суммы_двух_квадратов

(84) С применением объекта Match из 1C++ не плохо - 140 мс, но медленнее Брезенхема - 91 ms
Но в sqlite с начиная с версии 2021-03-12 (3.35.0) наконец завезли математические функции и материализованные представления.
Собрал с ними, получается 5 ms.


WITH RECURSIVE
const(N,N2) AS MATERIALIZED (SELECT 19451945,round(sqrt(19451945))),
cnt(x,y) AS (
    SELECT 1,1
    UNION ALL
    SELECT x+1,round(sqrt((SELECT N FROM const)-pow(x+1,2)))
    FROM cnt
    WHERE x<=(SELECT N2 FROM const)
)
SELECT
    x,y
FROM cnt
WHERE x*x + y*y = (SELECT N FROM const )


(41) :) тогда все вопросы к линусу