Fermat vs Pythagoras

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level.

This problem deals with computing quantities relating to part of Fermat’s Last Theorem: that there are no integer solutions of an+bn=cn for n > 2.

Given a positive integer N, you are to write a program that computes two quantities regarding the solution of

x2+y2=z2

where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file.

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <=N ). The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N . There should be one output line for each input line.

Input

10
25
100

Output

1 4
4 9
16 27

C Code

#include<stdio.h>  
#include<math.h>  
#include<string.h>  
#define min(a, b) (a<b?a:b)  
  
typedef long long INT;  
INT n, total;  
  
char ss[1000002];  
  
INT gcd(INT a, INT b) { return b?gcd(b,a%b):a; }  
  
void Cal() {  
    INT m , r, s, x, y, k, z;  
    INT up;  
    INT tri = 0, total = 0;  
    m = (INT)sqrt(n);  
    if(m*m < n) m++;  
    for(r = 1; r<= m; r++) {  
        up = min((n - r*r),r-1);  
        for(s = 1; s<= up; s++) {  
            x = r*r - s*s;  
            y = 2*r*s;  
            z = r*r + s*s;  
            if(x*x + y*y == z*z && z<=n) {  
                if(gcd(x,y) == 1) {  
                    tri++;  
                    for(k = 1; k*z<=n; k++) {  
                        ss[k*x] = 1;  
                        ss[k*y] = 1;  
                        ss[k*z] = 1;  
                    }  
                }  
            }  
        }  
    }  
    for(k = 1; k<= n; k++) {  
        if(ss[k] == 0) total++;  
        ss[k] = 0;  
    }  
    printf("%lld %lld\n",tri, total);  
}  
  
  
void main() {  
    while(scanf("%lld",&n) == 1) {  
        Cal();  
    }  
}