高橋くんと青木くんの好きな数を解いた


こんにちは、いなむーです。

AtCoderシリーズです。
今回はABC032のA問題「高橋くんと青木くんの好きな数」です。

問題はこちら。

問題文
青木君は整数 a で割り切れる数が好きです。 高橋君は整数 b で割り切れる数が好きです。

n 以上の整数で、青木君と高橋君の両方が好きな最小の数を答えてください。

入力
入力は以下の形式で標準入力から与えられる。

a
b
n
1 行目には、整数 a(1≦a≦100) が与えられる。
2 行目には、整数 b(1≦b≦100) が与えられる。
3 行目には、整数 n(1≦n≦20,000) が与えられる。
出力
出力は以下の形式で標準出力に行うこと。

1 行目に、n 以上の整数で青木君と高橋君の両方が好きな数の最小値を出力せよ。末尾の改行を忘れないこと。

この問題に対して、書いたコードがこちら。

class Favnum
  def inputnum
    @a, @b, @n = STDIN.read.split(?\n).map { | v | v.to_i }
  end
 
  def smallestnum
    self.inputnum
    if @a.between?(1,100) && @b.between?(1,100) && @n.between?(1,20000)
      i = @n
      while i >= @n
        if i% @a == 0 && i% @b == 0
          p i
          exit
        else
          i = i + 1
        end
      end
    end
  end
end
 
x = Favnum.new
x.smallestnum

最小公倍数を求めるっていうやつですね。
考えている途中で、最小公倍数を求めるメソッドがありそうって思ったのですが、なんだかアルゴリズム的な勉強になりそうだったので頑張って解いてみました。

まず、inputnumメソッドで、標準入力を順番に代入して、mapメソッドでintegerにします。
なお、split(?¥n)で行ごとに分解ししました。

そして、smallestnumメソッドで、betweenで特定の値の範囲にあることを条件とします。
それに合致した場合に、whileでぐるぐる回していきます。
回す条件として、aでもbで割り切れる値だったら出力する、割り切れなかったら1を足していくという風にしました。

これでなんとか回答できましたが、結構時間がかかってしまったのと、whileで回す条件が1足していっているので、無駄な計算が発生してしまってますね。
ここをなんとかしようと考えたら思いの外複雑になってきてしまったので、諦めました。
頭がスッとRuby脳というかプログラマー脳になるにはまだまだ時間がかかりそうです。

以上。