ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「ルート・パワー」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

自然数 n に対して、(1 + √2 + √3 + √5)n を展開して整理したものを考えます。

例えば、n = 2 のとき、(1 + √2 + √3 + √5)2 を展開して整理すると、11 + 2√2 + 2√3 + 2√5 + 2√6 + 2√10 + 2√15 となります。

このときの有理数の項の値は 11 です。

(1 + √2 + √3 + √5)n を展開して整理した有理数の項を F(n) と定義します。

例えば、F(2) = 11、F(3) = 31、F(12) = 577862325 です。
また、F(12) を 107 で割った余りは 7862325 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 1010)が与えられます。
標準出力に F(n) を 107 で割った余りの値を出力するプログラムを書いてください。

方針

平方根の和の n 乗を展開したものに関する問題です。3, 4 乗ぐらいなら手計算でも何とかできますが、それ以上となるとそうはいきません。さらに本問は n の最大が 1010 と非常に大きな値を扱います。これだけ大きな乗数でもうまく計算できる方法を考えていきましょう。

本問を解くための一つ目のポイントは、一つ手前の状態を考えることです。1 + √2 + √3 + √5 を n 乗したものと、n – 1 乗したものとの関係を見ていきましょう。そのために、(1 + √2 + √3 + √5)n を展開したものの 1, √2, √3, √5, √6, √10, √15, √30 の各係数を、an, bn, cn, dn, en, fn, gn, hn とおきます。

そして、(an-1,・・・, hn-1) と (an,・・・, hn) の間の関係を調べます。ようするに漸化式を導出するということです。(an,・・・, hn) は、 n – 1 のときの結果に 1 + √2 + √3 + √5 を掛け算して展開した時の各項の係数です。たいへん根気のいる作業ですが、次の計算で得ることができます。

このように、8 変数間の漸化式が得られました。単純には、初期値 (a0, b0, c0, d0, e0, f0, g0, h0) = (1, 0, 0, 0, 0, 0, 0, 0) から始めて、漸化式を繰り返し適用していけば、求めるべき an の値が得られます。コードは次のようになります(C++)。

#include <iostream>
using namespace std;
long long D = 10000000;

int main(int argc, char *argv[]) {
long long n;
cin >> n;

long long a = 1, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0;
long long a_new, b_new, c_new, d_new, e_new, f_new, g_new, h_new;
for (long long i = 1; i

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP