CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「アフター・ドット」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。

a÷b が有限小数となるような (a, b) の組の個数を求める問題です。
単純に解くと時間がかかり過ぎるので、高速化の方法を考えましょう。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

問題のおさらい

自然数 n に対し、1 ≦ an,1 ≦ bn を満たし、かつ小数で表した a÷b が有限小数となるような自然数の組 (a, b) の個数を F(n) と定義します。
(有限小数…小数点以下の桁数が有限である小数。)

例えば、F(3) = 7 です。
下記の (a, b) の組のうち、有限小数は太字で記した 7 個です。

  • 1÷1=1, 1÷2=0.5, 1÷3=0.33333…
  • 2÷1=2, 2÷2=1,  2÷3=0.66666…
  • 3÷1=3, 3÷2=1.5, 3÷3=1

同様に、F(5)=21,F(10)=68,F(100)=2185 となることが確かめられます。

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

方針

a÷b が有限小数となるような (a, b) の組の個数を求める問題です。問題文自体はいたってシンプルですが、解き方は一筋縄ではいきません。

単純に思いつく解法は、全ての (a, b) の組を列挙して、a÷b を実際に計算してみるという方法です。ですが、n の上限は 104 という条件です。最大で 104×104=108 個の組をチェックしなければなりません。これでは計算量的に大変ですので、高速化を考えましょう。

そのために必要となるのが、a÷b が有限小数になるってつまりはどういうこと? と考えることです。

実際にいくつかの組で試してみましょう。1÷2=0.5、1÷4=0.25、1÷5=0.5、1÷8=0.125、などは有限小数ですが、1÷3=0.333…、1÷6=0.166…、1÷7=0.142…、などは有限小数ではありません。ここから想像すると、分母が 2、5 以外の約数を持つなら、a÷b は有限小数となりそうです。

ただそれでは十分ではありません。例えば 3÷6 は、分母に 2、5 以外の約数の 3 を持ちますが、3÷6 自体は有限小数です。分子と分母の 3 とが約分で消えるためです。分母が 2、5 以外の因数を持っていたとしても、同じ因数が分子にあれば、a÷b は有限小数となります。

以上の考察をまとめます。ab が次のように表されれば、a÷b は有限小数となるということです。

分母を一つ固定しよう

では、そのような組 (a, b) の個数はどのように計算すればよいでしょうか。ここでは、始めに、分母 b の値を一つ固定してみましょう。固定した b の値を 2 で割り切れなくなるまで割っていきます。その商を今度は 5 で割り切れなくなるまで割っていきます。こうして得られた商は、上式の b の赤で囲った「2, 5 で割り切れない因数」に相当します。

次に分子 a に目をやります。右端の赤囲みの部分は、いま求めた値と同じです。それに (任意の自然数) を掛けたものが a になるわけですから、そのような a は 1 ≦ an の範囲にいくつ存在するかというと、floor(n ÷ (赤囲みの値)) 個だと分かります(floor():小数点以下を切り捨てる関数)。

結局、1 ≦ bn の範囲で変数 b をループで回して、上記の floor(n ÷ (赤囲みの値)) の値を足していけば、求めるべき答えが得られます。

コード例は以下です(C++)。

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    cin >> n;
    int answer = 0;
    for (int b = 1; b <= n; b ++) {
        int m = b;
        while (m % 2 == 0) m /= 2;
        while (m % 5 == 0) m /= 5;
        answer += n / m;
    }
    cout << answer << endl;
}

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)今回は、単純にクリアするだけではなく、コードゴルフ(コードの文字数をできるだけ短くできるか?)や、高速化(パラメータ n の値をどこまで大きくできるか?)にチャレンジして下さった方が多くいらっしゃいました。一体どんな発想で短く&早くできるのか、ぜひチェックしてみて下さい!

CodeIQ「アフター・ドット」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
Kawazoeさんの次の問題にご期待ください。

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

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたの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

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