SRM508 Div1 Easy - DivideAndShift

問題

n個の箱の左からm番目を開けたいが、Manaoはいま一番左にある箱を開けることしかできない
以下の操作を最小何回行えば目的を達成できるか
1) 箱をp(=nの素因数)分割し、目的の箱を含む区間だけ残し、n/pを新しいnとする
2) 箱の列を1だけ左/右にシフトする

解法

n<=10^6のとき素因数の個数はたかだか19個だから操作1で割る素因数の組み合わせを全部試せる
(割る素因数の個数)+(その後目的達成に必要なシフト回数) の最小値を求めればいい

実装

nを素因数分解し、素因数の組み合わせを全列挙

class DivideAndShift {
	public:
	vector<int> pf(int n) {
		vector<int> res;
		for (int i = 2; i*i <= n; i++) {
			while (n%i==0) {
				res.push_back(i);
				n /= i;
			}
		}
		if (n!=1) res.push_back(n);
		return res;
	}
	
	int getLeast(int n, int m) {
		m--;
		vector<int> p = pf(n);
		int res = inf;
		rep(i,1<<p.size()) {
			int nn = n, mm = m;
			rep(j,p.size()) if (i>>j&1) nn /= p[j];
			mm %= nn;
			chmin(res, __builtin_popcount(i) + min(mm, nn-mm));
		}
		return res;
	}
};