simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

Rubyで全ての約数を出すメソッドを作った

「How Many Divisors?」
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_D

AOJの問題を解いてて「約数の配列だして、upper_boundとlower_boundをとれば終わりやな」と思ったのですが、Rubyに今の要素全部無かったので、作りました。

require 'prime'

class Integer
  def divisor_list
    return [] if self <= 0
    return [1] if self == 1

    prime_division.map{|e| [*(0..e.last)].map{|v| e.first ** v }}.inject{|res, e| res.map{|t| e.map{|v| t * v}}.flatten}.sort
  end
end

class Array
  def upper_bound(val)
    a = 0
    b = size

    while a < b
      c = (( a + b ) / 2 ).to_i

      if val < at(c)
        b = c
      else
        a = c + 1
      end
    end

    b
  end

  def lower_bound(val)
    a = 0
    b = size

    while a < b
      c = (( a + b ) / 2 ).to_i

      if val <= at(c)
        b = c
      else
        a = c + 1
      end
    end

    b
  end
end

class Solver
  def initialize
    a, b, c = gets.chomp.split(' ').map(&:to_i)

    divisor_list = c.divisor_list

    n = divisor_list.lower_bound(a)
    m = divisor_list.upper_bound(b)

    puts m - n
  end
end

Solver.new

Array#bsearchの返り値が添字なやつがほしい...