Educational Codeforces Round 184 (Rated for Div. 2) D 题解

[Educational Codeforces Round 184 (Rated for Div. 2)](https://codeforces.com/contest/2169)

D2. Removal of a Sequence (Hard Version)

Question

给你 $x,y,k(x,y,k\le {10}^{12})$ ，有一个 $1\sim {10}^{12}$ 的自然数列，执行 $x$ 次以下操作，一次操作为：

删除第 $y,2y,3y,\cdots ,my\le n$ 个位置的数，$n$ 是序列长度

输出操作之后第 $k$ 个位置的数，不合法则输出 $-1$

Solution

学到了一种成套方法

某一轮轮第 $k$ 个地方的数在前一轮的位置是 $k+\lfloor \frac{k-1}{y-1}\rfloor$，我们设 $r=\lfloor \frac{k-1}{y-1}\rfloor$

我们发现对于多个连续的 $k$，$r$ 的值都是相同的，所以可以一起算

当前这一轮为 $k$，往后 $\alpha$ 轮后的 $k^{\prime }$ 就是 $k^{\prime }=k+\alpha r$，满足 $\lfloor \frac{k^{\prime }-1}{y-1}\rfloor >r$，也就是 $k^{\prime }>(r+1)(y-1)$，联立得到 $\alpha$ 的范围 $\alpha >((r+1)(y-1)-k)/r$

所以每次对 $\alpha$ 轮一起处理，直到 $x$ 被减为 $0$

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 MX = 1e12;

void solve() {
    i64 x, y, k; cin >> x >> y >> k;
    if (y == 1) {cout << -1 << '\n'; return ;}
    i64 n = x;
    while (n > 0) {
        i64 r = (k - 1) / (y - 1);
        if (r == 0) { cout << k << '\n';return ; }
        i64 a = min(((r + 1) * (y - 1) - k) / r + 1, n);
        n -= a; k += a * r;
        if (k > MX) {cout << -1 << '\n'; return ;}
    }
    cout << k << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; cin >> t;
    while (t--) solve();
    return 0;
}