#author("2017-10-11T20:33:20+09:00","default:nobuoki","nobuoki")
* 問題（和訳） [#v580c44a]
Problem 75 「1通りの整数直角三角形」
https://goo.gl/bQ9FGg

* 回答 [#p4fc38c0]
awk 'function gcd(p,q){if(q==0)return p;else return gcd(q,p%q)}BEGIN{for(n=1;n<866;n++)for(m=n+1;m<=866;m+=2)if(gcd(m,n)==1){L=2*m*m+2*m*n;for(i=1;i<=1500000/L;i++)print L*i}}' | awk '{a[$1]++}END{for(v in a)if(a[v]==1)b++;print "answer: "b}'

* 実行結果 [#ma47c6e0]
#pre{{
answer: 161667

real    0m8.442s
user    0m8.710s
sys     0m0.160s
}}

* 解説 [#n29c23ec]
原始ピタゴラス数を求め、その倍数含めいくつあるかを計算する
https://goo.gl/YFS4jD ピタゴラスの定理 - Wikipedia

自然数の組 (a, b, c) が原始ピタゴラス数であるためには、ある自然数 m, n が
  * m と n は互いに素（m と n の最大公約数は 1）
  * m > n
  * m − n は奇数
を満たすとき、
  (a, b, c) = (m^2 − n^2, 2mn, m^2 + n^2)
の関係がある

m, n の探索範囲は、
三角形の長さの和 = 2*m^2 + 2mn <= 1,500,000 なので、
n=1のときmは最大だから 2m(m+1) <= 1,500,000
したがって                   m <= sqrt(1,500,000/2) = 866 となる

#prism(bash){{{{
#!/bin/sh

awk '
# 最大公約数を求める関数（ユークリッドの互除法）
function gcd(p,q){
  if(q==0)
    return p;
  else
    return gcd(q,p%q)
}BEGIN{
  # 力技で探索
  # n: 1  <= n <866
  # m: n+1<= m <=866
  for(n=1;n<866;n++)
    for(m=n+1;m<=866;m+=2)

      # 原始ピタゴラス数の条件: mとnは互いに素
      if(gcd(m,n)==1){

        # 以下、デバッグ用
        #a=m^2-n^2;
        #b=2*m*n;
        #c=m^2+n^2;

        # 長さを求める
        L=2*m*m+2*m*n;

        # 原始ピタゴラス数の整数倍を含め、Lを出力
        for(i=1;i<=1500000/L;i++)
          print L*i

          # デバッグ用
          #print L*i,m,n,a*i,b*i,c*i
      }
}' |

# 1度しか現れないL(=$1)の数が答え
awk '{a[$1]++}END{for(v in a)if(a[v]==1)b++;print "answer: "b}'
}}}}
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS