yukicoder：No.141 魔法少女コバ

問題

https://yukicoder.me/problems/no/141

数学問題。以下のいずれかの操作ができるとき、 1 から m/n にするまでにかかる操作の最小回数を求めよ。

操作
1. a を a+1 にする
2. a を 1/a にする

考え方

逆から考えていく。すなわち以下の操作ができるとする。

操作
1. a を a-1 にする
2. a を 1/a にする

m は負にはなりえない。m < n の場合は 1 の操作はできないので 2 の操作をする。逆に m > n の場合、 2 の操作をしても結局もとの数に戻るので 2 の操作をする意味はない。無限ループになる。よって 1 の操作をする。この時、単純にシミュレーションするとm が n に比べて非常に大きい場合に時間がかかりすぎる。結局引くことのできる最大の回数は m / n で求めることができ、引いたあとの数は m % n となる。割り切れる場合は 0 になる手前の n になる場合に一致する。

   public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int m = in.nextInt(), n = in.nextInt();
        long s = 0;

        while (m != n) {

            if (m > n) {
                s += m/n;
                m %= n;
                if (m == 0) {
                    s--;
                    break;
                }
            } else {
                int t = m;
                m = n;
                n = t;
                s++;
            }
        }
        System.out.println(s);
    }

ポイント

• 引き算の回数は、剰余を考えると効率化できる。

類題