eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ферма против Пифагора

Ферма против Пифагора

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Компьютерная помощь в доказательстве и проверке теорем занимают небольшую нишу в области компьютерных наук. Первое доказательство проблемы 4-х красок было завершено с помощью компьютерной программы и в настоящее время усилиями в области подобного контроля удалось достичь более высокого уровня проверки уже на уровне процессоров.

Эта задача касается вычислительных величин, относящихся к части теоремы Ферма о том, что нет целочисленных решений уравнения a^n + b^n = c^n для n > 2.

Учитывая заданное положительное целое число N, Вы должны написать программу, которая помогает вычислять решения уравнения x^2 + y^2 = z^2, где x, y и z натуральные числа меньшие или равные N. Вы должны вычислить количество троек (x, y, z) таких, что x < y < z, и они взаимно просты, т. е. не имеют общих делителей больших 1. Вы также должны вычислить число значений 0 < pN таких, что p не является частью любой такой тройки (а не только взаимно простых троек).

Giriş verilənləri

Входные данные состоят из последовательности натуральных чисел, по одному в строке. Каждое число во входных данных не превышает 1000000. Ввод данных продолжается до конца файла.

Çıxış verilənləri

Для каждого натурального N выведите 2 целых числа, разделённых одним пробелом. Первое число показывает количество взаимно простых троек, удовлетворяющих условию задачи (таких что каждая компонента тройки ≤ N). Второе число это количество натуральных чисел, таких что все они ≤ N и не являющихся компонентой троек для всех троек, созданных для всех чисел ≤ N. Каждая пара чисел выводится в отдельной строке.

Nümunə

Giriş verilənləri #1
10
25
100
Çıxış verilənləri #1
1 4
4 9
16 27