Codeforces Round #201 (Div. 1) C. Number Transformation II
なるほど…
解法
kmjp さんの解法を参考にしました。
int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<int> x(n); for (int i = 0; i < n; i++) cin >> x[i]; sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); int z = 0; int a, b; cin >> a >> b; while (1) { if (a <= b) break; int y = 1; int size = x.size(); for (int i = size-1; i >= 0; i--) { int w = a%x[i]; if (a-w < b) { swap(x[i], x[size-1]); size--; } else { y = max(y, w); } } x.resize(size); a -= y; z++; } cout << z << endl; return 0; }