POJ 1305 - Fermat vs. Pythagoras

http://poj.org/problem?id=1305

概要

与えられた整数 \(N\) に対し，\(0 < x < y < z \le N \land x ^ 2 + y ^ 2 = z ^ 2\) を満たす整数 \((x, y, z)\) の三つ組について考える． これらの三つ組のうち，\(x, y, z\) がそれぞれ互いに素であるものの数と，どの三つ組にも含まれない整数 \(0 < p \le N\) の数を答える．

制約

• \(0 < N \le 10 ^ 6\)

解法

この三つ組はいわゆるピタゴラス数である． ピタゴラス数を実際に全列挙して，求められているものの数を数えるだけ．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int gcd(int a, int b)
 6 {
 7   int r;
 8   while ((r = a % b) != 0) {
 9     a = b;
10     b = r;
11   }
12   return b;
13 }
14 
15 int main()
16 {
17   int N;
18   while (cin >> N) {
19     int x = 0;
20     static bool v[1000001];
21     fill_n(v, 1000000, false);
22     for (int n = 1; n*n < N; n++) {
23       for (int m = n+1; n*n + m*m <= N; m += 2) {
24         if (gcd(m, n) == 1) {
25           ++x;
26           const int a = m*m - n*n, b = 2*m*n, c = m*m + n*n;
27           for (int d = a, e = b, f = c; f <= N; d += a, e += b, f += c) {
28             v[d] = v[e] = v[f] = true;
29           }
30         }
31       }
32     }
33     int y = 0;
34     for (int i = 1; i <= N; i++) {
35       if (!v[i]) {
36         ++y;
37       }
38     }
39     cout << x << ' ' << y << endl;
40   }
41   return 0;
42 }