Ферма проти Піфагора#1156

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

1 секунда

64 мегабайти

Легка

Комп'ютерно згенеровані та асистовані докази займають окрему нішу в інформатиці. Перший доказ проблеми чотирьох кольорів був виконаний за допомогою комп'ютерної програми, а теперішні зусилля дозволили досягти перевірки на рівні процесора.

Ця задача стосується обчислення значень, пов'язаних із частиною Великої теореми Ферма, а саме ствердження, що не існує цілих розв'язків рівняння $a^{n} + b^{n} = c^{n}$ a^n + b^n = c^n для $n > 2$ n > 2.

Задано додатнє ціле число $N$ , потрібно написати програму, яка знаходить два значення щодо розв'язків рівняння $x^{2} + y^{2} = z^{2}$ x^2 + y^2 = z^2, де $x$ , $y$ і $z$ — додатні цілі числа, не більші за $N$ . Знайдіть кількість трійок $(x, y, z)$ (x, y, z) таких, що $x < y < z$ x < y < z, і $x$ , $y$ , $z$ — взаємно прості (не мають спільного дільника більшого за $1$ ). Також обчисліть кількість чисел $0 < p \leq N$ 0 < p \le N, які не входять до жодної такої трійки (не лише до взаємно простих трійок).

Вхідні дані

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

Вихідні дані

Для кожного $N$ у вхідних даних виведіть два цілих числа через пробіл: кількість взаємно простих трійок $(x, y, z)$ (x, y, z) (де кожен компонент не більший за $N$ ), і кількість додатних цілих чисел, не більших за $N$ , які не є компонентом жодної трійки додатних цілих, не більших за $N$ . Кожну пару виводьте в окремому рядку.

Приклади

Приклад 1