Ферма проти Піфагора
Комп'ютерна допомога у доведенні та перевірці теорем займають невелике нішу в області комп'ютерних наук. Перше доведення проблеми 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. Кожна пара чисел виводиться у окремому рядку.