プロジェクトオイラー39. ~ Integer right triangles ~

No.39 Integer right triangles

問題.

Q. 周の長さがであって，3辺の長さが整数である直角三角形は，例えばのときちょうど3つ存在する：

において，このような直角三角形の個数が最大となるを求めよ．

考え方とプログラム例(c++)

辺の長さが整数である直角三角形の辺の長さは，

と書けます．ここで，は互いに素な整数で，一方が偶数，もう一方が奇数，は自然数ととることで，辺の長さが整数である直角三角形はの組と1対1に対応します．このとき，周の長さはとなります．

互いに素かどうかについては，最大公約数を求める場合と同じように再帰を使いました．

#include<bits/stdc++.h>
using namespace std;

int N = 1000;

int coprime(int a, int b){//互いに素なら1, 互いに素でなければ0を返す
  if(a % b == 0){
    if(b == 1)
      return 1;
    else
      return 0;
  }
  else
    return coprime(b, a % b);
}

int main(){
  vector<int> cnt(N+1, 0);
  for(int m = 1; m * m < N; m++){
    for(int n = 1; n < m; n++){
      if((m + n) % 2 == 0 || !coprime(m, n))
        continue;
      int p = 2 * m * (m + n);
      for(int k = p; k <= N; k += p)
        cnt[k] += 1;
    }
  }
  int ans = 0;
  for(int i = 1; i <= N; i++){
    if(cnt[i] > cnt[ans]){
      ans = i;
    }
  }
  cout << ans << endl;
  return 0;
}