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

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

Новые блоги и статьи Все статьи Все блоги /
BitTorrent (версия 7.11 English) и Меню Настройки russiannick 15.11.2026 Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language	Транслитерация текста с кириллицы на латиницу (вариант №4) Maks 15.11.2026 Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .	BitTorrent (версия 4.3.9) и Меню Настройки russiannick 15.11.2026 В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение	Транслитерация текста с кириллицы на латиницу (вариант №3) Maks 15.11.2026 Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .

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

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

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

Решение