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

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

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

Для заданного натурального 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)
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
#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, рад тебя видеть :)

Новые блоги и статьи Все статьи Все блоги /
Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .	сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .
сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .	Сукцессия 20. Война автоботов. Делаем ставки. Лёд против "пш-пш!". anaschu 11.07.2026 Битва ИИ в ризосфере: Как мы скрестили жесткие ОДУ, закон Фика и «подземный шантаж» Уважаемые коллеги! Хочу поделиться уникальным опытом ведения междисциплинарной компьютерной разработки. Прямо. . .	Сукцессия 19. Какие выводы я сделал из модели? Часть 2.Внутримикоризный стехиометрический буфер и хроно-дискретные зоны экспансии anaschu 11.07.2026 Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования	Сукцессия 18. Какие выводы я сделал из войны грибов с деревьями? Часть 1- рассказ и немного про термины anaschu 11.07.2026 Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования Система ОДУ описывает динамику изменения массы различных компонентов системы во времени. Ключевой. . .

@Danielive 0 / 0 / 0 Регистрация: 12.09.2014 Сообщений: 24

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

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

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	26.09.2015, 21:36
	SlavaSSU, для 3 и 9 у вас нет решений. А они - есть ) И чего у вас выводится в ans? 0

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

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

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

Решение