Решение задачи

@misterGay · Регистрация: 06.09.2020

Студворк — интернет-сервис помощи студентам

Дан массив или лист, его длина кратна 4 и число P высчитывается так {(arr[i]^2 + arr[i+1]^2)*((arr[i+2]^2+arr[i+3]^2)*...}
Нужно найти такие числа A и B, чтобы A^2 + B^2 = P, при этом A и B целые положительные числа не равные 0. Нельзя использовать перебор, как это сделал я =( так как при очень больших числах, например как то, что представлено в моем коде ниже, программа чуть ли не зависает. Например с примером {2, 1, 3, 4} программа справляется легко, как и с примерами по сложнее, но когда число слишком большое, то время на перебор уходит очень много. Нужно обойтись без перебора.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.company;
 
 
import java.math.BigInteger;
 
public class Main
{
 
    public static BigInteger[] solve(int[] arr)
    {
        BigInteger p = BigInteger.valueOf(1l);
        BigInteger a, b;
        int n = (int)(Math.pow(arr[0],2) + Math.pow(arr[1],2));
 
       for (int i = 0; i < arr.length; i += 2)
            p = BigInteger.valueOf(p.longValue()*(long)(Math.pow(arr[i], 2) + Math.pow(arr[i + 1], 2)));
 
       a = BigInteger.valueOf(Math.round(Math.sqrt(p.doubleValue()/n*Math.pow(arr[0],2))));
       b = BigInteger.valueOf(Math.round(Math.sqrt(p.doubleValue()/n*Math.pow(arr[1],2))));
 
        while (true)
        {
            BigInteger a_plus_b = BigInteger.valueOf((long)Math.pow(a.doubleValue(),2) + (long)Math.pow(b.doubleValue(),2));
            if (a_plus_b.equals(p))
                break;
            a = a_plus_b.doubleValue() < p.doubleValue()?BigInteger.valueOf(a.longValue()+1):a;
            b = a_plus_b.doubleValue() >= p.doubleValue()?BigInteger.valueOf(b.longValue()-1):b;
        }
 
        System.out.printf("-->[%d]<--\n", p);
 
        return new BigInteger[]{a, b};
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 5, 4, 4, 5, 5, 4, 2, 4, 7, 6, 5, 9, 8, 7, 6, 5, 4, 9, 6, 5, 7, 9, 5, 8, 9, 6, 8, 4, 9, 2, 5, 5, 3, 9, 7, 9, 2, 6, 3, 2};
 
        BigInteger[] out_numbers = solve(arr);
 
        System.out.printf("[%d, %d]\n", out_numbers[1], out_numbers[0]);
 
        System.out.println();
    }
}

@Coffeini · 17.06.2021, 04:18

Повтори еще десять раз, что перебор нежелателен...
Ты P неправильно рассчитываешь.
Вообще еще куча теорем по этому поводу есть... Как пример: https://en.wikipedia.org/wiki/... es_theorem
Как я вижу, проще всего просто подобрать число A или B, а потом по этому числу найти оставшееся.
Ну или постепенно вычитать нечетные числа из P, пока оно не станет квадратом. А числа, которые вычитались сами образуют квадрат... Т.к. любой квадрат в своей сущности лишь сумма нечетных чисел...
1 = 1
1 + 3 = 4
1 + 3 + 5 = 9
И т.д.

@misterGay · 17.06.2021, 10:33 **[ТС]**

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

@Coffeini · 17.06.2021, 11:06

Сообщение от misterGay

Число P я считаю вполне себе верно

Сомневаюсь. В процессе вычисления ты переводишь его в long. Т.е. при достаточно большом P, что выходит за пределы long, будет округление по 2⁶⁴. А если P всегда меньше 2⁶⁴, то BigIteger и вовсе не стоит использовать, т.к. он очень сильно тормозит программу.

Добавлено через 1 минуту
По хорошему здесь хватит multiply(BigInteger)

@misterGay · 17.06.2021, 12:04 **[ТС]**

А, вы про это. Здесь вы правы, это я заметил и исправил =)

Добавлено через 35 минут
Получился вот такой код, он вроде исправно работает, проходит довольно экстренные тесты, на codewars все тесты проходит, кроме итогового. Выводит непонятную ошибку, как я полагаю проблема где-то в моем коде, есть в нем видимо сильный недостаток, надеюсь вы его увидите

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package com.company;
 
 
import java.math.BigInteger;
 
public class Main
{
 
    public static BigInteger[] solve(int[] arr)
    {
        BigInteger p = BigInteger.valueOf(1l);
        BigInteger a = BigInteger.valueOf(0l), b = BigInteger.valueOf(0l);
 
        for (int i = 0; i < arr.length; i += 2)
            p = p.multiply(BigInteger.valueOf((long)(Math.pow(arr[i], 2) + Math.pow(arr[i+1], 2))));
 
        for (int i = 1;p.longValue()>0;i+=2)
        {
            p = p.add(BigInteger.valueOf(-i));
            b = b.add(BigInteger.valueOf(i));
            a = BigInteger.valueOf((long)Math.sqrt(p.doubleValue()));
            if (p.doubleValue() == a.multiply(a).doubleValue())
            {
                b = BigInteger.valueOf((long)Math.sqrt(b.doubleValue()));
                break;
            }
        }
 
        return new BigInteger[]{a, b};
    }
 
    public static void main(String[] args)
    {
        int[] arr = {5, 4, 4, 5, 5, 4, 2, 4, 7, 6, 5, 9, 8, 7, 6, 5, 4, 9, 6, 5, 7, 9, 5, 8, 9, 6, 8, 4, 9, 2, 5, 5, 3, 9, 7, 9, 2, 6, 3, 2};
 
        BigInteger[] out_numbers = solve(arr);
 
        System.out.printf("[%d, %d]\n", out_numbers[1], out_numbers[0]);
 
        System.out.println();
    }
}

@Coffeini · 17.06.2021, 12:26

Сообщение от misterGay

if (p.doubleValue() == a.multiply(a).doubleValue())

Для операций сравнения в Biginteger есть compareTo()

Сообщение от misterGay

BigInteger.valueOf((long)Math.sqrt(p.dou bleValue()));

Вероятно тут p не убирается в long.
Смотрю в BigInteger не завезли sqrt, поэтому или попробуй его реализовать сам: https://habr.com/ru/post/469561/
Ну или поищи готовые рабочие реализации.

@misterGay · 17.06.2021, 13:07 **[ТС]**

В BigInteger в последних версиях есть sqrt -- не сразу заметил. Постарался сделать так, чтобы ничего не урезалось, но к сожалению число <1418415758805549309928181280000000000 > программа не может представить в виде суммы двух квадратов, цикл уходит в бесконечное плаванье =(

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package com.company;
 
 
import java.math.BigInteger;
 
public class Main
{
 
    public static BigInteger[] solve(int[] arr)
    {
        BigInteger p = BigInteger.valueOf(1l);
        BigInteger a = BigInteger.valueOf(0l), b = BigInteger.valueOf(0l);
 
        for (int i = 0; i < arr.length; i += 2)
            p = p.multiply(BigInteger.valueOf((long)(Math.pow(arr[i], 2) + Math.pow(arr[i+1], 2))));
 
        System.out.printf("%d", p);
 
        a = p.sqrt();
        if (p.equals(a.multiply(a)))
            return new BigInteger[]{a, b};
 
        for (BigInteger i = BigInteger.valueOf(1l);p.longValue()>0;i = i.add(BigInteger.valueOf(2l)))
        {
            p = p.add(i.multiply(BigInteger.valueOf(-1l)));
            b = b.add(i);
            a = p.sqrt();
            if (p.compareTo(a.multiply(a)) == 0)
            {
                b = b.sqrt();
                break;
            }
        }
        return new BigInteger[]{a, b};
    }
 
    public static void main(String[] args)
    {
        int[] arr = {5, 4, 4, 5, 5, 4, 2, 4, 7, 6, 5, 9, 8, 7, 6, 5, 4, 9, 6, 5, 7, 9, 5, 8, 9, 6, 8, 4, 9, 2, 5, 5, 3, 9, 7, 9, 2, 6, 3, 2};
 
        BigInteger[] out_numbers = solve(arr);
 
        System.out.printf("[%d, %d]\n", out_numbers[1], out_numbers[0]);
 
        System.out.println();
    }
}

@Coffeini · 17.06.2021, 13:27

Сообщение от misterGay

p.longValue()>0

Потери возможны.
Да и я не понимаю, что за константы(11, 21, -11 и пр.)

@xoraxax · 17.06.2021, 13:29

...

@misterGay · 17.06.2021, 14:03 **[ТС]**

Про какие именно константы речь? Я немного не догнал. А с потерями, я не знаю как задать условие без парсинга biginteger. Он не позволяет использовать операторы сравнения к biginteger

Добавлено через 1 минуту

Сообщение от xoraxax

...

Вы как эксперт по java, что можете сказать по поводу моего решения? Только без излишнего негатива, пожалуйста

@xoraxax · 17.06.2021, 14:25

считай в BigInteger, не надо туда сюда переводить

@Coffeini · 17.06.2021, 15:02

Сообщение от misterGay

как задать условие

p.compareTo(BigInteger.ZERO) > 0

Сообщение от misterGay

Про какие именно константы речь?

Сообщение от misterGay

BigInteger.valueOf(1l)

Сообщение от misterGay

BigInteger.valueOf(2l)

Сообщение от misterGay

BigInteger.valueOf(-1l)

А. Это же L. Ну есть BigInteger.ONE, BigInteger.TWO для этого.

@misterGay · 17.06.2021, 15:36 **[ТС]**

Теперь мой код выглядит так, но к сожалению вышеописанное число всё ещё не может быть представлено в виде суммы двух квадратов

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package com.company;
 
 
import java.math.BigInteger;
 
public class Main
{
 
    public static BigInteger[] solve(int[] arr)
    {
        BigInteger p = BigInteger.ONE;
        BigInteger a = BigInteger.ZERO, b = BigInteger.ZERO;
 
        for (int i = 0; i < arr.length; i += 2)
            p = p.multiply(BigInteger.valueOf((long)(Math.pow(arr[i], 2) + Math.pow(arr[i+1], 2))));
 
        a = p.sqrt();
        if (p.compareTo(a.multiply(a)) == 0)
            return new BigInteger[]{a, b};
 
        for (BigInteger i = BigInteger.ONE; p.compareTo(BigInteger.ZERO)>0;i = i.add(BigInteger.TWO))
        {
            p = p.add(i.multiply(BigInteger.valueOf(-1)));
            b = b.add(i);
            a = p.sqrt();
            if (p.compareTo(a.multiply(a)) == 0)
            {
                b = b.sqrt();
                break;
            }
        }
        
        return new BigInteger[]{a, b};
    }
 
    public static void main(String[] args)
    {
        int[] arr = {5, 4, 4, 5, 5, 4, 2, 4, 7, 6, 5, 9, 8, 7, 6, 5, 4, 9, 6, 5, 7, 9, 5, 8, 9, 6, 8, 4, 9, 2, 5, 5,
                3, 9, 7, 9, 2, 6, 3, 2};
 
        BigInteger[] out_numbers = solve(arr);
 
        System.out.printf("[%d, %d]\n", out_numbers[1], out_numbers[0]);
 
        System.out.println();
    }
}

@Coffeini · 17.06.2021, 23:13

Сообщение от misterGay

число всё ещё не может быть представлено в виде суммы двух квадратов

Ну не может и не может. Право, не корову же потерял...
Ну а если потерял, то почитай вот это: http://www.mathnet.ru/links/02... /mp195.pdf

Добавлено через 4 минуты
Почему эта ссылка ip-ник мой палит... Меня же теперь взломают...( М-да.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Coffeini 753 / 370 / 133 Регистрация: 01.02.2020 Сообщений: 1,096 Записей в блоге: 1
	17.06.2021, 04:18
	Повтори еще десять раз, что перебор нежелателен... Ты P неправильно рассчитываешь. Вообще еще куча теорем по этому поводу есть... Как пример: https://en.wikipedia.org/wiki/... es_theorem Как я вижу, проще всего просто подобрать число A или B, а потом по этому числу найти оставшееся. Ну или постепенно вычитать нечетные числа из P, пока оно не станет квадратом. А числа, которые вычитались сами образуют квадрат... Т.к. любой квадрат в своей сущности лишь сумма нечетных чисел... 1 = 1 1 + 3 = 4 1 + 3 + 5 = 9 И т.д. 0

@misterGay 1 / 1 / 0 Регистрация: 06.09.2020 Сообщений: 34
	17.06.2021, 10:33 [ТС]
	Число P я считаю вполне себе верно, для этой задачи было несколько тестов, которые я прошел. Число P высчитывалось верно. В остальном спасибо, поработаю с полученной информацией 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	17.06.2021, 13:29
	Сообщение было отмечено korvin_ как решение Решение ... Миниатюры 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	17.06.2021, 14:25
	считай в BigInteger, не надо туда сюда переводить 0