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; } };