Ферма против Пифагора
Компьютерная помощь в доказательстве и проверке теорем занимают небольшую нишу в области компьютерных наук. Первое доказательство проблемы 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 < p ≤ N таких, что p не является частью любой такой тройки (а не только взаимно простых троек).
Входные данные
Входные данные состоят из последовательности натуральных чисел, по одному в строке. Каждое число во входных данных не превышает 1000000. Ввод данных продолжается до конца файла.
Выходные данные
Для каждого натурального N выведите 2 целых числа, разделённых одним пробелом. Первое число показывает количество взаимно простых троек, удовлетворяющих условию задачи (таких что каждая компонента тройки ≤ N). Второе число это количество натуральных чисел, таких что все они ≤ N и не являющихся компонентой троек для всех троек, созданных для всех чисел ≤ N. Каждая пара чисел выводится в отдельной строке.