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

@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-ник мой палит... Меня же теперь взломают...( М-да.

Новые блоги и статьи Все статьи Все блоги /
AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .

@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