プロジェクトオイラー Problem 75 「1通りの整数直角三角形」 †

Problem 75 「1通りの整数直角三角形」 †

ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである. 他にも沢山の例が挙げられる.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Lを鉄線の長さとする. 直角三角形を作るときに1通りの折り曲げ方しか存在しないような L ≤ 1,500,000 の総数を答えよ.

注: この問題は最近変更されました. あなたが正しいパラメータを使っているか確認してください.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2075

解法
原始ピタゴラス数とその定数倍が150万以下のものをカウントするだけです。


#include<stdio.h>
const int LIMIT=1500*1000;
int counts[LIMIT+1]={0};
int gcd ( int a, int b ){
      int c;
      while ( a != 0 ) {
            c = a; a = b%a;  b = c;
      }
      return b;
}



int main(){
      int m=2;
      while(2*m*(m+1)<=LIMIT){
            int n=1;
            while(2*m*(m+n)<=LIMIT&&n<m){
                  if(((m-n)%2==0)||(gcd(m,n)!=1)){
                        //何もしない
                  }else{
                        int d=1;
                        while(2*m*(m+n)*d<=LIMIT){
                              counts[2*m*(m+n)*d]++;
                              d++;
                        }
                  }
                  n++;
            }
            m++;
      }
      int ans=0;
      for(int i=1;i<=LIMIT;i++){
            ans+=(counts[i]==1);
      }
      printf("%d\n",ans);
}