CodeIQ 挑戦の記録 : 「アフター・ドット」問題

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160707020612p:plain

問題文を要約すると下記の通り

  • 自然数 {n} に対し、{1 \leq a \leq n} , {1 \leq b \leq n} を満たし、かつ小数で表した {a \div b} が有限小数となるような自然数の組 {(a, b)} の個数を {F(n)} と定義する。
    （有限小数…小数点以下の桁数が有限である小数。）
  • 標準入力から {n} が与えられる。{F(n)} を解答する。
  • {1 \leq n \leq {10}^{4}}

方針

自然数 {a, b} について、以下の条件が成り立つ時、{a \div b} は有限少数になる。

  • aがbの倍数である場合。
  • bが1か2か5かの内のいずれか1つまたはいずれかの複数だけの積である場合。
    (1か2か5以外の素数を含まない)

よって、{1 \leq a \leq n} , {1 \leq b \leq n} において、{b} が {{ 1,2,5 }} のいずれかの積で 構成される整数の場合は、 {a \div b} が有限少数になる {a} は {n} 個ある。
素因数分解して {{ 1,2,5 }} 以外の素数を含む合成数については、 {{ 2,5 }} で割り切れるだけ割った時の 商の倍数の個数だけ {n} 個中に {a} が存在する。

これより、{1} から {n} までの整数について、{2} と {5} で割り切れるだけ割り、商 {m} について {n} 個中の個数 {n \div m} を求め、これの総和を解答とする。

なお、{2} と {5} で割り切れるだけ割る方法について、入力の最大値 {{10}^{4}} までの整数に 含まれる可能性のある2と5の積の最大値との最大公約数を取り、検査値を最大公約数で割る事によって、{2} と {5}の因数を取り除く。
{{10}^{4}} を超えない最大の{2} のべき乗は {log_2 10000} {= 13.28...} なので {13}
{{10}^{4}} を超えない最大の{5} のべき乗は {log_5 10000} {= 5.72...} なので {5}

よって、{{2}^{13} \times {5}^{5}} {= 256 \times {10}^{5}} との最大公約数を取れば良いが、
文字数削減の都合上、 {{20}^{8}} ( {{2}^{16} \times {5}^{8}} {= 256 \times {10}^{8}} ) との最大公約数を取る事にする。
これにより、{n = {10}^{5}} までは正確に答えが出る。

実装 (Ruby ・ 50byte)

p (0..n=gets.to_i).inject{|s,i|s+i.gcd(20**8)*n/i}

Ruby では Enumerable#inject というメソッドがある。
（reduce という別名もあり）
配列などの要素をブロックの中で繰り返し計算する事に使う便利なメソッドであるが、ブロック中で変数を宣言して使う時、 初期値を明示的に指定しないと、最初の要素が初期値として扱われ、2番目以降の要素が計算の対象となる。
今回は範囲オブジェクトの要素を計算しているが、最初の要素を「1」とするとb=1の時が計算されない。「0」としても初期値としてこれに加算されるだけなので、ゼロ割りは発生しない。
今回は良いが注意が必要である。

では、


Sponsored Link