« 「マイナー・ゲーム問題」の高度じゃないコード | トップページ | 「アフター・ドット問題」の高度じゃないコード(高速編) »

2016年7月 7日 (木)

「アフター・ドット問題」の高度じゃないコード(ゴルフ編)

「高度じゃないコード」シリーズその14は「アフター・ドット問題」です。今回の記事は、高速編がでかくなりそうなので、前編・後編と2回に分けますが、その前編(ゴルフ編)です。

自然数 n に対し、1 ≦ a ≦ n,1 ≦ b ≦ n を満たし、かつ小数で表した a÷b が有限小数となるような自然数の組 (a, b) の個数を F(n) と定義します。
(有限小数…小数点以下の桁数が有限である小数。)
標準入力から、自然数 n(1 ≦ n ≦ 104)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

最初に、a ÷ b が有限小数となるための条件を考えます。どんな自然数でも、2 のべき乗と 5 のべき乗で割ると有限小数となるので、b を 2 と 5 で割れるだけ割ります。そして、a がその商 b' の倍数であれば有限小数になります。1 ≦ a ≦ n におけるその個数は、n ÷ b' の整数部ということになります。後は、1 ≦ b ≦ n の条件でループさせれば、F(n) を求めることができます。

今回は、ゴルフ解を作って一旦終了したように思えましたが、自然数 n(1 ≦ n ≦ 104)の制限を外し、どこまで大きな値まで計算できるかを競うことになり、非常に悩みましたがとても楽しませていただきました。

ということで、まずはゴルフ解です。何度かの改良の後にできた Ruby(51) がこれです。

ここで、i.gcd(40**8) というのは、i と 40**8(408)の最大公約数なので、2 と 5 で割れるだけ割ることができる最大の値です。そして、後者は、この方法で計算できるのが n = 1,500,000 程度(ただし、実行くんでは 40**8 を外へ出さないと「Time limit exceeded.」となる)なので、そこから逆算した定数です。この n 以下で最大の 2 のべき乗は 220、5 のべき乗は 58 です。つまり、使える数は、これ以上のべき乗の積となります。

220 × 58 = ( 23 × 5 )8 ÷ 24 = 408 ÷ 24

なので、5文字に納まることから 40**8 を使用しました。

しばらくの間、これ以上の短縮は無理かと思っていましたが、ふと、b = 1(コード中では i = 1)の場合の個数は n 個だということに気付きました。ということで、Ruby(49) ができました。

怒涛の後編(高速編)につづく・・・。

|

« 「マイナー・ゲーム問題」の高度じゃないコード | トップページ | 「アフター・ドット問題」の高度じゃないコード(高速編) »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63881483

この記事へのトラックバック一覧です: 「アフター・ドット問題」の高度じゃないコード(ゴルフ編):

« 「マイナー・ゲーム問題」の高度じゃないコード | トップページ | 「アフター・ドット問題」の高度じゃないコード(高速編) »