Codeforces Round #201 (Div. 1) C. Number Transformation II

なるほど…

問題

codeforces.com

解法

kmjp さんの解法を参考にしました。

kmjp.hatenablog.jp

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