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

@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, рад тебя видеть :)

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

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

	Найти разложение натурального числа на сумму квадратов трёх целых чисел 26.09.2015, 01:03. Показов 4606. Ответов 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

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

Решение