2012年8月20日

UVa 106 - Fermat vs. Pythagoras

We have to know a formula before doing this problem.
This problem will be very easy by using this formula!

#include <stdio.h>

int gcd (int a, int b) {
  while ((a %= b) && (b %= a));
  return a + b;
}

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int i, j, ans = 0, part = 0;
    bool *have = new bool[n + 1];
    for (i = 0; i <= n; i++)
      have[i] = 0;
    for (i = 1; i * i < n; i++) {
      for (j = i + 1; (i * i + j * j) <= n; j += 2) {
        if (gcd(i, j) != 1) continue;
        int a = 2 * j * i, b = j * j - i * i, c = j * j + i * i;
        ans++;
        int A = a, B = b, C = c;
        while (C <= n) {
          if (!have[A]) part++;
          if (!have[B]) part++;
          if (!have[C]) part++;
          have[A] = 1;
          have[B] = 1;
          have[C] = 1;
          A += a;
          B += b;
          C += c;
        }
      }
    }
    printf("%d %d\n", ans, n - part);
    delete[] have;
  }
  return 0;
}

沒有留言:

張貼留言