CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「エース・ナンバー」問題解説

2015.10.29 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 11
  • このエントリーをはてなブックマークに追加

「数学の問題をプログラミングで解こう!」シリーズ。
本問より解説を書かせていただきます。

本問、皆さんはうまくクリアできたでしょうか?
できた方もそうでない方も、ぜひチェックして下さい!
by @riverplus Kawazoe

問題のおさらい

整数 n に対して、16 進数の A を n 個並べた数を F(n) と定義します。

例えば、F(5) は 16 進数で AAAAA です。この数を 10 進数で表すと 699050 です。
同様に、F(10) を 10 進数で表すと 733007751850 です。この数を 106 で割った余りは 751850 です。

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

方針

巨大な16進数の数を10進数に変換したときの下6桁を求める問題です。ほとんどのプログラミング言語では16進数→10進数の変換を行う関数が用意されています。が、今回は最大でAが 1010 個連なる巨大な数を扱います。普通のPCのメモリにはとうてい収まりません。別の方法を考えましょう。

そこでまず、よく知られている16進数→10進数の変換の方法を用います。低い桁から始めて、各桁の値と16のべき乗をかけたものを足し合わせます。

10でまとめて少しきれいな形になりました。何となく、1から始めて、16を次々とかけていったものを 106 で余りを取りながら足していけば良さそうに見えます。が、それでも n 回の掛け算・足し算を行わなければなりません。計算量としてはまだまだ大きいので、さらに工夫が必要です。

以下、2種類の方法を紹介します。

方法1:周期性を利用する

問われているのは 106 で割った余りだけである点に注目します。16x mod 106x:整数)は、高々 106 通り(有限個)の値しか取りません。ですので、x の値を大きくしていけば、どこかで過去のいずれかの値と一致するような x が存在するはずです。さらにそこから先は同じ値をたどるはずですので、同じ結果になる部分をまとめてやれば、以降の計算を一気に省略することができます。

そのような x を見つける方法はいくつかあります。実際に実験するのが手っ取り早いでしょう。16x mod 106 をキー、x を値としたペアを保存して16を次々と掛け算していくのが一つの方法です。ほか、フロイドの循環判定法も有用です。

参考:フロイドの循環判定法(Wikipedia)

以下のコードは、16x mod 106x のペアを配列で保存しながら周期を探します。ほか、C++ではstd::mapが便利です。

#include <iostream>
using namespace std;
int D = 1000000;
int c[1000000];

int main() {
    int a = 1, p = 0, q = 0;
    for (int i = 0; i < D; i++) c[i] = -1;
    for (;; p ++) {
        if (c[a] != -1) break;
        c[a] = p;
        a = (a * 16) % D;
    }
    q = c[a];
    p -= q;
    cout << "数列 a(n) = 16^n mod 10^6 は, n=" << q << " 以降, 周期 " << p << " で循環する." << endl;
    cout << "つまり, a(n+" << p << ") = a(n) (ただし, n≧" << q << ")." << endl;
}

このコードを実行すると、次の結果が得られます。

数列 a(n) = 16^n mod 10^6 は, n=2 以降, 周期 3125 で循環する.
つまり, a(n+3125) = a(n) (ただし, n≧2).

つまり、こういうことです。n = 100000 の場合を例にしています。

n がどれだけ大きな数であっても、周期3125のカタマリが何個あるか(赤囲みの個数)と、カタマリ一つあたりの値(1つの赤囲みの和を mod 106 したもの)が分かれば、計算すべき範囲を一気に狭められます。あとは端数部分(青囲みの部分)を計算すれば、最終的な答えが得られます。

以上のコードをこちらに示します。

方法2:等比数列の和を利用する

もう一つの方法は、F(n) を等比数列の和として見るやり方です。等比数列の和の公式はよく知られています。

参考:等比数列(Wikipedia)

適用し整理すると次のようになります。

まずは右辺を 106 で割った余りを求めます。これはべき剰余として知られており、O(log n) で高速に算出できます。

参考:冪剰余(Wikipedia)

ここから先がちょっと厄介です。つい、左辺 3・F(n) の 3 を落とすつもりで、上記のべき剰余の結果を 3 で割り算してしまいたくなるところですが、いわゆる合同式でその計算は不適切です。正しくは、106 を法とする 3 の逆元を求め、それを両辺に掛けます。拡張ユークリッドの互除法という方法と関連します。

参考:整数の合同と1次合同式(外部ページ)

以上のコードをこちらに示します。3 の逆元に関しては下記を参考にしました。

参考:一次合同式を解く(外部ページ)

逆元を求める以外の方法も紹介します。こちらは比較的シンプルです。右辺の剰余を求める際に、106 でなく 3・106 での剰余を求めることがポイントです。この剰余を R とおくと、3・F(n) = (整数)×3・106 + R と書けます。両辺を 3 で割ると、F(n) = (整数)×106 + R/3 となり、求めるべき答えは R/3 に等しいと分かります。

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)今回紹介した以外にもいろいろな解き方があると思います。ぜひ多くの人のコードを見て学んで下さい!

CodeIQ「エース・ナンバー」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 11
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

@riverplus Kawazoe

数学・パズル好きのソフトウェアエンジニアです。某社で研究開発をしています。Project Euler の問題開発チームメンバー(最近はあまり活動せず)。twitter: @riverplus Web Site: riverplus.net

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ