CodeIQ：アフター・ドット

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「アフター・ドット」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
自然数 n に対し、1 ≦ a ≦ n，1 ≦ b ≦ n を満たし、かつ小数で表した 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) の値を出力するプログラムを書いてください。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

require 'prime'

$CYCLE = [0,1]

def getCycle(i)
	ret = 1
	for v in i.prime_division
		if v[0] != 2 && v[0] != 5 then
			ret *= v[0] ** v[1]
		end
	end

	return ret
end

def makeCycle()
	for i in 2..10000
		$CYCLE << getCycle(i)
	end
end

def solve(n)
	ret = 0
	for i in 1..n
		ret += n / $CYCLE[i]
	end
	return ret
end

#main
makeCycle()

while line = gets
	line.strip!
	if(line.empty?) then next end
	n = line.to_i
	p solve(n)
end

解説

プログラミング能力というよりも数学的に解けるかという方が重要な問題です。

考え方

Rubyの場合、Rationalがあるので総当たりでできるなら非常に簡単ですが、総当たりすると108もあるので時間的にとても無理です。
まず、有限少数になる条件は分母が2n5m(n,m≧0)の場合です。この条件を利用することは明らかに思えます。

とりあえず何か法則でもないかと思って1〜10までで手書きしてみました。
割り切れる場所が○、割り切れない場所が×です。
分子
12345678910
分母
1 ○○○○○○○○○○
2 ○○○○○○○○○○
3 ××○××○××○○
4 ○○○○○○○○○○
5 ○○○○○○○○○○
6 ××○××○××○○
7 ××××××○×××
8 ○○○○○○○○○○
9 ××××××××○×
10 ○○○○○○○○○○

2と5以外の素数が分母の時に割り切れないのは当然です。
注目すべきは3と6と9の行です。これらを見てわかるのは有限少数になるサイクルは分母を素因数分解し、2と5以外の数の積の周期で有限少数になる値が出現するのではないか、ということです。6は2×3なので3の倍数ごとに有限少数になり、9は32なので9の倍数ごとに有限少数になるということです。

この考え方に基づいてコーディングします。

makeCycle()

この関数は$CYCLEの添字が分母の時、幾つ周期で有限少数になるかの表を作るための関数です。入力値nまでを求めれば良いのですが、どうせ最悪のケースはテストケースに存在するはずなので10000まで求めてしまいます。

getCycle()である数の周期を計算します。
値を素因数分解して2と5以外の数を掛け合わせれば周期になります。
Rubyは素因数分解を求める機能がprimeライブラリにあって標準で使えるので簡単です。

solve()

答えを求める関数です。
nを$CYCLEの各要素で割った商が$CYCLEの添字を分母とした時に有限少数になる数の数になります。なのでそれを足し合わせれば答えになります。

雑感

提出していませんがRationalを使った単純なプログラムを最初に作っています。
目的は2つあって、1つは考え方が正しいことを確認するため、もう一つは投稿用のプログラムの結果が正しいことを確認するためです。遅くてダメなことがわかっているプログラムでもロジックが単純で結果が正しいことという確信の持てるプログラムを作って本番用のプログラムの結果をチェックしたり、考え方が正しいかを確認するために使うというのは結果として早く、正しいプログラムを書くために有用な手段だと思います。