SRM508 Div1 Easy - DivideAndShift

問題

　 $N$ 個の箱が順番に並んでおり、左から $M$ 個目に目的のものが入っている。開けられる箱は一番左のものだけであり、箱の列に対しては次の操作が行える。

$N$ 以下の素数 $p$ について、 $M$ を $M % (N / p)$ 、 $N$ を $N / p$ で置き換える。
箱全体を $N$ 右か左に一つずらす。両端はループしているとする。

　上のいずれかの操作を繰り返し、目的にものを一番左に持っていく最小の操作回数を求めよ。

解法

　最終的に割る数が決まっているとき、割る操作を全て先に行い、シフトは最後にまとめて行えばよい。したがって $N$ を素因数分解して何回素因数で割るかを計算し、そこで得られた新しい $n, m$ についてシフトによる操作の必要数を求めていけば良い。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class DivideAndShift {
public:
    int getLeast(int N, int M) {
        M--;
        auto fact = getFactor(N);
        vector<ll> num(fact.size(), 0);
        auto update = [&]() {
            for (ll i = fact.size() - 1; i >= 0; i--) {
                if (num[i] != fact[i].second) {
                    num[i]++;
                    for (ll j = i + 1; j < fact.size(); j++) {
                        num[j] = 0;
                    }
                    return true;
                }
            }
            return false;
        };

        ll ans = INT_MAX;
        while (true) {
            ll p = 1;
            ll op_num = 0;
            for (ll i = 0; i < num.size(); i++) {
                p *= pow(fact[i].first, num[i]);
                op_num += num[i];
            }

            ll curr_n = N / p;
            ll curr_m = M % curr_n;

            ans = min(ans, curr_m + op_num);
            ans = min(ans, curr_n - curr_m + op_num);

            if (!update()) {
                break;
            }
        }

        return ans;
    }
private:
    vector<pair<ll, ll>> getFactor(int N) {
        vector<pair<ll, ll>> fact;
        for (ll i = 2; i <= (ll)N; i++) {
            if (!isPrime(i)) {
                continue;
            }
            ll num = 0;
            while (N % i == 0) {
                N /= i;
                num++;
            }
            if (num) {
                fact.push_back({ i, num });
            }
        }
        return fact;
    }
    bool isPrime(ll n) {
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
};