Educational Codeforces Round #184

D2

题目大意：从自然数序列 $1,2,\ldots,10^{12}$ 开始，连续进行 $x$ 次操作；每次在当前序列中同时删除位置为 $y,2y,3y,\ldots$ 的元素。求操作结束后第 $k$ 个数，如果剩余长度小于 $k$ 则输出 $-1$ 。

数据范围：$1 \leq t \leq 10, 1 \leq x,y,k \leq 10^{12}$

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    ll x, y, k;
    cin >> x >> y >> k;
    if (y == 1) {
        cout << -1 << endl;
        return;
    }
    for (ll i = 0; i < x;) {
        ll tem = (k - 1) / (y - 1);
        if (tem == 0) break;
        ll R = (tem + 1) * (y - 1) + 1;
        ll cnt = (R - k + tem - 1) / tem;
        k += min(cnt, x - i) * tem;
        i += min(cnt, x - i);
        if (k > 1e12) {
            cout << -1 << endl;
            return;
        }
    }
    cout << k << endl;
    return;
}