数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

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

No.39 Integer right triangles

問題.

Q. 周の長さが $p$ であって，3辺の長さが整数 $\{a, b, c\}$ である直角三角形は，例えば $p=120$ のときちょうど3つ存在する：

$\begin{align*} \{20, 48, 52\}, \{24, 45, 51\}, \{30, 40, 50\} \end{align*}$

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

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

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

$\begin{align*} (a, b, c) = (k(m^2-n^2), 2kmn, k(m^2+n^2)) \end{align*}$

と書けます．ここで， $m, n$ は互いに素な整数で，一方が偶数，もう一方が奇数， $k$ は自然数ととることで，辺の長さが整数である直角三角形は $(k, m, n)$ の組と1対1に対応します．このとき，周の長さは $a+b+c=2m(m+n)$ となります．

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

#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;
}

京大2022年度理系第3問

入試問題

問題．

$n$ を自然数とする．3つの整数 $n^2+2, n^4+2, n^6+2$ の最大公約数 $A_n$ を求めよ．

$n^2+2, n^4+2, n^6+2$ は因数分解できないので，互除法を使って考えることになります．

ユークリッドの互除法
$A$ を $B$ で割ったときの余りを $C$ とするとき， $A$ と $B$ の最大公約数は $B$ と $C$ の最大公約数に等しい

解説．

まず， $n^4+2, n^6+2$ を $n^2+2$ で割ったときの余りをそれぞれ求めると，

\begin{align*}
n^4+2 &= (n^4-4)+6\\
&= (n^2+2)(n^2-2)+6\\
n^6+2 &= (n^6+8)-6\\
&= (n^2+2)(n^4-2n^2+4)-6
\end{align*}

よって，最大公約数 $A_n$ は $n^2+2$ と $6$ の最大公約数に等しい．

さらに， $n^2+2$ を6で割ったときの余りを $R_n$ とすると， $A_n$ は $R_n$ と $6$ の最大公約数に等しい．

あとは， $n$ を6で割った余りで場合分けして調べていきます．

(i) $n=6m$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m)^2+2\\
&= 6\cdot 6m+2
\end{align*}
より， $R_n=2$ であり， $A_n=2$ .

(ii) $n=6m\pm 1$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m\pm 1)^2+2\\
&= 6(6m^2\pm 2m)+3
\end{align*}(複号同順)
より， $R_n=3$ であり， $A_n=3$ .

(iii) $n=6m\pm 2$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m\pm 2)^2+2\\
&= 6(6m^2\pm 4m+1)
\end{align*}(複号同順)
より， $R_n=0$ であり， $A_n=6$ .

(iv) $n=6m+3$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m+3)^2+2\\
&= 6(6m^2+6m+1)+5
\end{align*}
より， $R_n=5$ であり， $A_n=1$ .

したがって，(i)〜(iv)より，
$n$ を $6$ で割った余りが0のとき $A_n=2$
1,5のとき $A_n=3$
2,4のとき $A_n=6$
3のとき $A_n=1$

追記

$n$ を6で割った余りが1, 5のとき，および2,4のときをまとめて計算していますが，これは場合分けをする前に具体的な $n$ の値 $n=1, 2, 3, 4, 5, 6$ の場合を計算してみることで，まとめて扱ってよいかどうかを判断できます．