SRM 508 div1 easy:DivideAndShift

SRM練習会に参加。easyは解けてもよかったのですがしょうもないミスをして0完になってしまいました。

問題

TopCoder Statistics - Problem Statement

解法

最初に割り算して個数を減らしてからシフトをしていくのが有利。
どのタイミングからシフトを始めるのかはよくわからないのでそこは全探索する。
計算量が若干心配ですが,問題ありません。探索範囲はNの素因数の数に依存しますが,素数がp種類のときに探索範囲がp倍になるだけです。あんまり種類を増やそうとすると2*3*5*7*11*13とかですでにNの制限に引っかかりそうなのでそれほど種類は増えません。そのようなことを考えると探索範囲が最大になるのは6^m*2^pのような形でかけるときになりそうですがこの時も探索範囲は(2^m)*pといったところなのでたいしたことにはなりません。
本番やらかしたのはdfsの最後のfor文でm%tmpと書くべきところをm%=tmpと書いてdfsを呼んでいたところです。

const int MAXN = 1000100;
int prime[MAXN];
int ans;

void dfs(int n, int m, int d) {
    if (n == 1) {
        ans = min(ans, d);
        return;
    }
    ans = min({ans, d+m, d+n-m});
    set<int> p;
    {
        int tmp = n;
        while (prime[tmp] != 0) {
            p.insert(prime[tmp]);
            tmp /= prime[tmp];
        }
        p.insert(tmp);
    }
    for (int el : p) {
        int tmp = n/el;
        dfs(tmp, m%tmp, d+1);
    }
}

class DivideAndShift {
public:
    int getLeast(int N, int M) {
        prime[0] = prime[1] = 1;
        for (int i = 2; i < MAXN; i++) {
            if (prime[i] == 0) {
                for (int j = 2; j * i < MAXN; j++) {
                    prime[i*j] = i;
                }
            }
        }
        ans = MAXN;
        dfs(N, M-1, 0);
        return ans;
    }
};