「ルート・パワー」問題解答 ( CodeIQ )

はじめに

CodeIQというところでプログラミング問題「ルート・パワー」に解答しましたので、ネタバレです。

codeiq.jp

問題

入力 n に対して、$(1+\sqrt{2}+\sqrt{3}+\sqrt{5})^n$ を計算した場合の ( $\sqrt{整数}$の1次式と見たときの ) 有理数部分 ( ただし 107で割った余り ) を出力する、という問題です。

codeiq.jp

解説

いやえっと。コードは既に公開済みですし、ちょっと旬を逃した感がありますが…。 上で挙げたCodeIQマガジンの記事にある、行列計算による解法と同じです。C++により剰余計算つき ( 剰余環Z/nZ上の ) 行列クラスを設け、べき乗の計算をおこなうものです。

いや、最初Rubyで組もうと思ったのですが ( もちろんRubyでも組めますが )、行列ライブラリ matrix をそっくり剰余環に流用する方法が分からなくて、一から実装するんなら…というところがあったのですね。

ちなみに、行列による計算は ( 線形代数に慣れた人には ) 表現が完結ですが、無駄が多いようです。$(1+\sqrt{2}+\sqrt{3}+\sqrt{5})^n$は、有理数に様々な平方根を添加した拡大体 ( 数学ガール第5巻ガロア理論で触れられています…たしか ) の要素とみなせますから、体の乗算を直接実装した方が ( $\sqrt{整数}$ の種類が増えた場合に ) 少ない計算量で済ませることができるようです。

最後に

行列計算自体はすぐ思いついたのですが、剰余環上での固有値は求まらないし、簡略化する方法が分からずgolfは断念しました…。

他の方のコードはいつもの通り、togetterにまとめがありますので、そちらもどうぞ。

togetter.com