著名的費馬大定理是指：當n>2時，xn+yn=zn 無整數解，這邊我們要處理的問題跟費馬大定理有點關係。

給你一個正整數 N，你的任務是算出兩個與方程式 x2+y2=z2 的解相關的數字。( 0 < x < y < z <= N )

第一個數字是互質的數對(triples) (x,y,z) 數目。互質是指 x、y、z 沒有大於 1 的公因數。第二個數字p是在 小於等於 N 的數字內不屬於任何數對 (x,y,z) 的正整數總數，這邊 x、y、z不需要互質。

例如，N=10，可找到一組 互質數對 (3,4,5)  及 一組不互質的數對 (6,8,10)， 1、2、7、9 共 4 個數字沒用到。所以N=10要輸出1與4。

Input

輸入含有多組測試資料，每組測試資料一列，有一個正整數 N （1 <= N <= 1000000）

Output

輸出一列，含兩個整數，如題目所述，數字中間以一個空白字元分隔。

Sample Input
10
25
100
500
1000000
Sample Output
1 4
4 9
16 27
80 107
159139 133926

#include"stdio.h"
#include"math.h"
#include"string.h"
int mark[1000000];
int prime(int x,int y)
{
   for(int i=2;i<=x;i++)
   {
      if(x%i==0&&y%i==0)  return 0;
   }
   return 1;
}

int main()
{
   int n;
   int m1,m2;
   int x,y,z;
   int cnt;
   while(scanf("%d",&n)!=EOF)
   {
      memset(mark,0,sizeof(mark));
      cnt=0;m1=0;m2=0;
      for(x=3;x<=n;x++)
      {
        for(y=x+1;y*y+x*x<=n*n;y++)
        {
           z=(int)floor(sqrt((double)(x*x+y*y)));
           if(x*x+y*y==z*z)
           {
              if(prime(x,y)&&prime(z,y)&&prime(x,z))
              cnt++;
              mark[x]=1;
              mark[y]=1;
              mark[z]=1;
           }
           if(x*x+y*y==(z+1)*(z+1))
           {
              if(prime(x,y)&&prime(z+1,y)&&prime(x,z+1))
              cnt++;
              mark[x]=1;
              mark[y]=1;
              mark[z+1]=1;
           }
        }
      }
      for(x=1;x<=n;x++)
      {
         if(mark[x]==0)     m1++;
      }
      printf("%d %d\n",cnt,m1);
   }
   return 0;
}

同志们啊！