Задача о Пифагоровых тройках

@motocross971 · Регистрация: 30.03.2017

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

Добрый день. Думаю, многие решали эту задачу просто методом перебора для небольших значений. В данном случае, необходимо при заданном c (гипотенуза) найти все тройки взаимно простых чисел a, b, c, таких, что a*a + b*b = c*c.
При 0 < с < 10^6. Как ни крутил, не выходит O(n), быть может, есть какая-то математическая хитрость. Заранее спасибо !

@Case-Man · 17.07.2017, 21:47

С катетом проще, он либо $https://www.cyberforum.ru/cgi-bin/latex.cgi?{m}^{2}-{n}^2$ либо $https://www.cyberforum.ru/cgi-bin/latex.cgi?2mn$
В обоих случаях факторизация и почти никакого перебора

@Ромаха · 18.07.2017, 01:08

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

так не годится, гипотенуза ограничивает диапазон катетов, а от катета в поисках другого можно вдоль числовой прямой до второго пришествия шагать

Мимо

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

А если имеем заданный катет n < 10^8 и необходимо вывести все возможные прямоугольные треугольники ( где a, b, c не обязательно взаимно простые ), этот алгоритм также применим ?

Я бы делал не совсем так.
10^8 операций должно зайти.
Тогда просто a^2+b^2 = c^2
Отсюда получаем, что a^2 = (c-b)(c+b)

Теперь давайте факторизуем a^2
И для каждого числа у нас есть два варианта - соотнести его с первым или вторым множителем.
Дальше все супер очевидно.
Итог - 2^(количество простых)
А максимальное кол-во простых - log2(a^2)
Тогда получается чистый a^2
И если дан катет, а не его квадрат - то словим tl.
Значит извлечем корень. Ничего не изменится. Снова красота.

Точно есть и другие решение, но это мне больше нравится.

@motocross971 · 23.08.2017, 23:28 **[ТС]**

Ромаха, не совсем понял Ваш метод. К тому же факторизация числа - довольно скользкая тема. Даже если включим тест на простоту, может оказаться, что число является произведение 2-х простых чисел( или 2-х простых и некого составного ), тогда уже будет слишком долго, а вероятностные алгоритмы использовать нельзя, т.к необходим всегда точный ответ.

"Сверху" гипотенузу ограничивает значение a^2 / 2, что в худшем случае 10е16, поэтому методы перебора, даже если использовать бинарный поиск не помогут.

Новые блоги и статьи Все статьи Все блоги /
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .

@motocross971 0 / 0 / 0 Регистрация: 30.03.2017 Сообщений: 36

	Задача о Пифагоровых тройках 17.07.2017, 15:37. Показов 4514. Ответов 22 Метки нет (Все метки) Добрый день. Думаю, многие решали эту задачу просто методом перебора для небольших значений. В данном случае, необходимо при заданном c (гипотенуза) найти все тройки взаимно простых чисел a, b, c, таких, что *aa + bb = cc**. При 0 < с < 10^6. Как ни крутил, не выходит O(n), быть может, есть какая-то математическая хитрость. Заранее спасибо ! 0

@Case-Man 167 / 107 / 22 Регистрация: 02.01.2012 Сообщений: 596
	17.07.2017, 21:47
	С катетом проще, он либо $https://www.cyberforum.ru/cgi-bin/latex.cgi?{m}^{2}-{n}^2$ либо $https://www.cyberforum.ru/cgi-bin/latex.cgi?2mn$ В обоих случаях факторизация и почти никакого перебора 0

@motocross971 0 / 0 / 0 Регистрация: 30.03.2017 Сообщений: 36
	23.08.2017, 23:28 [ТС]
	Ромаха, не совсем понял Ваш метод. К тому же факторизация числа - довольно скользкая тема. Даже если включим тест на простоту, может оказаться, что число является произведение 2-х простых чисел( или 2-х простых и некого составного ), тогда уже будет слишком долго, а вероятностные алгоритмы использовать нельзя, т.к необходим всегда точный ответ. "Сверху" гипотенузу ограничивает значение a^2 / 2, что в худшем случае 10е16, поэтому методы перебора, даже если использовать бинарный поиск не помогут. 0