Fermat vs. Pythagoras

## 题目描述 计算机自从被发明以来，在计算机科学的辅助证明等领域占有了一席之地。地图四染色问题首次被完全证明就是在计算机的协助下完成的。当今，从高级语言级别到芯片级别的翻译都要借助于计算机。 现在，这道题需要你计算一些有关费马大定理 ($a^n+b^n=c^n$在$n>2$时无整数解)的计数类问题。 给你一个正整数N,你需要编写程序计算下面方程的解的个数： $x^2+y^2=z^2$ 其中x,y,z都是不大于N的正整数，你需要计算： 1.满足上述方程且满足$x<y<z$的互质三元组的个数 2.任意满足上述方程的三元组都不包含的正整数p ($0<p\leq n$) 的个数 (三元组不需互质，元素不大于N) ## 输入格式 输入包含一系列正整数N (每行一个)。输入文件中的任意正整数都不大于$1000000$。end-of-file标志着输入文件的结束。 ## 输出格式 对于每一个N，输出两个用空格隔开的正整数。第一个整数是互质正整数三元组的个数 (三元组中任意元素都小于等于N)。第二个整数是不大于N且不出现在任何元素不大于N的三元组中的正整数的个数。 每个输入行需要对应一个输出行。 Translated by @boshi

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=42 [PDF](https://uva.onlinejudge.org/external/1/p106.pdf) 



10
25
100

1 4
4 9
16 27