Найти разложение натурального числа на сумму квадратов трёх целых чисел

@Danielive · Регистрация: 12.09.2014

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

Для заданного натурального N (0 < N ≤ 10^9) вычислить число троек целых чисел (x, y, z),
таких, что x^2 + y^2 + z^2 = N.

Помогите понять цель этого задания и каковы методы решения этой задачи

@~~IrineK~~ · 26.09.2015, 21:15

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

и сказал что нет таких троек

Таки нет (см пост 13)
8 сек - это максимальный прогон по всем циклам. Отлично )

@SlavaSSU · 26.09.2015, 21:18

IrineK, ну я хотел чтобы вы именно у себ я запустили, компы у всех разные. например я запустил этот код на сайте одном и он за секунду посчитал для 999999937

@~~IrineK~~ · 26.09.2015, 21:36

SlavaSSU, для 3 и 9 у вас нет решений.
А они - есть )

И чего у вас выводится в ans?

@SlavaSSU · 26.09.2015, 21:45

IrineK, ага, вот так тогда.

C++ (Qt)

#include <iostream>
#include <cmath>
#include <ctime>
 
using namespace std;
 
const int LIM = 4e4; 
int sqrs[LIM + 1];
 
int main() {
    int n;
    cin >> n;
    double start = clock();
    int ans = 0;
    for(int i = 1; i <= LIM; i++) sqrs[i] = i * i;
    int n1 = n / 3;
    for(int i = 1; sqrs[i] <= n1; i++) {
        int nn = n - sqrs[i];
        int n2 = (nn >> 1);
        for(int j = i; sqrs[j] <= n2; j++) {
            int k = int(sqrt(double(nn - sqrs[j])));
            ans += (k * k == nn - sqrs[j]);
        }
    }
 
    cout << ans << endl;
    cout << "TIME == " << (clock() - start) / CLOCKS_PER_SEC << " s" << endl;
    return 0;
}

ans - колво троек (i, j, k) таких что
1) i >= 1, j >= 1, k >= 1;

2) i <= j && j <= k;

@~~IrineK~~ · 26.09.2015, 22:00

SlavaSSU,
Для 999999999 - прогон по всем циклам - 9 сек
Для 999999937 - с выводом всех 4268 решений в файл (а чё добру пропадать?) - 19 сек

Отличная идея с сохранением квадратов.
Поздравляю )

Danielive, а вам нужно будет дополнить решение поста 24 анализом на перестановки (расширение на разный порядок возрастания x,y,z) и знаки (расширение на целые числа). Рецепт - в посте 3.

@_Ivana · 26.09.2015, 23:03

SlavaSSU, ну понятно, с мемоизацией в глобальном массиве будет быстрее - это примерно то же, что я про хеш писал

Для задачи и любого из предложенных алгоритмов совершенно пофигу простота чисел. И да, 7 секунд против 28 это конечно в 4 раза быстрее, но не сказать что на порядок

Не по теме:

ЗЫ SlavaSSU, рад тебя видеть :)

@~~IrineK~~ Заблокирован
	26.09.2015, 22:00	25
	SlavaSSU, Для 999999999 - прогон по всем циклам - 9 сек Для 999999937 - с выводом всех 4268 решений в файл (а чё добру пропадать?) - 19 сек Отличная идея с сохранением квадратов. Поздравляю ) Danielive, а вам нужно будет дополнить решение поста 24 анализом на перестановки (расширение на разный порядок возрастания x,y,z) и знаки (расширение на целые числа). Рецепт - в посте 3. 1

@Danielive 0 / 0 / 0 Регистрация: 12.09.2014 Сообщений: 24
		1
	Найти разложение натурального числа на сумму квадратов трёх целых чисел 26.09.2015, 01:03. Показов 3761. Ответов 25 Метки нет (Все метки) Для заданного натурального N (0 < N ≤ 10^9) вычислить число троек целых чисел (x, y, z), таких, что x^2 + y^2 + z^2 = N. Помогите понять цель этого задания и каковы методы решения этой задачи 0

@~~IrineK~~ Заблокирован
	26.09.2015, 21:15	21
	Сообщение от SlavaSSU и сказал что нет таких троек Таки нет (см пост 13) 8 сек - это максимальный прогон по всем циклам. Отлично ) 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	26.09.2015, 21:18	22
	IrineK, ну я хотел чтобы вы именно у себ я запустили, компы у всех разные. например я запустил этот код на сайте одном и он за секунду посчитал для 999999937 0

@~~IrineK~~ Заблокирован
	26.09.2015, 21:36	23
	SlavaSSU, для 3 и 9 у вас нет решений. А они - есть ) И чего у вас выводится в ans? 0

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	26.09.2015, 23:03	26
	SlavaSSU, ну понятно, с мемоизацией в глобальном массиве будет быстрее - это примерно то же, что я про хеш писал Для задачи и любого из предложенных алгоритмов совершенно пофигу простота чисел. И да, 7 секунд против 28 это конечно в 4 раза быстрее, но не сказать что на порядок Не по теме: ЗЫ SlavaSSU, рад тебя видеть :) 1

Найти разложение натурального числа на сумму квадратов трёх целых чисел

Решение