問題(和訳)

Problem 75 「1通りの整数直角三角形」
https://goo.gl/bQ9FGg

回答

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}'

実行結果

answer: 161667

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

解説

原始ピタゴラス数を求め、その倍数含めいくつあるかを計算する
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 となる

#!/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
Last-modified: 2019-03-24 (日) 07:44:02