106.c

/* @JUDGE_ID: 26089BN 106 C "" */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int gcd(int i, int j) {
  int r;
  while (j != 0) {
    r = i % j;
    i = j;
    j = r;
  }
  return i;
}

int main() {
  int N, n;
  int x, y, z;
  int i, j, k;
  int count = 0;
  int included = 0;
  int *part;

  while(scanf("%d", &N) == 1) {
    /* initialize */
    count = 0;
    included = 0;
    n = (int)sqrt(N) + 1;

    part = (int *)malloc(sizeof(int) * N);

    for (i = 0; i < N; i ++) {
      part[i] = 0;
    }

    for (i = 1; i < n; i ++) {
      for (j = 1; j < i; j ++) {
        x = i * i - j * j;
        y = 2 * i * j;
        z = i * i + j * j;
        if (x > N || y > N || z > N
            || !(gcd(x, y) == 1 && gcd(x, z) == 1 && gcd(y, z) == 1)) {
          continue;
        }
        count ++;
        for (k = 1; !(x * k > N || y * k > N || z * k > N); k ++) {
          if (part[x * k - 1] == 0) {
            part[x * k - 1] = 1;
            included ++;
          }
          if (part[y * k - 1] == 0) {
            part[y * k - 1] = 1;
            included ++;
          }
          if (part[z * k - 1] == 0) {
            part[z * k - 1] = 1;
            included ++;
          }
        }
      }
    }

    printf("%d %d\n", count, N - included);
    free(part);
  }
}