Educational Codeforces Round 184 (Rated for Div. 2)

A - Alice and Bob

D2 - Removal of a Sequence (Hard Version)

妈的，被 Hack 数据搞了

考虑第 $i$ -th 迭代的位置 $p$ 与第 $i+1$ -th 迭代的位置 $p'$ . 对于 $p'$ 之前的每 $y-1$ 个位置，都是上一轮迭代里的 $p$ 个位置删掉一个形成的. 所以

p\gets p'+\lfloor\frac{p'-1}{y-1}\rfloor \\ p'\gets p-\lfloor\frac{p}{y}\rfloor

初始时， $p=O(V)$ . 我们直接考虑数论分块：

如果 $y-1\lt \sqrt{V}$ ，那么对于第二行的式子而言，每次都会减去 $\frac{p}{y}\gt \sqrt{V}$ ，所以最多 $O(V)$ 轮. 而又由于一式其实就是二式的 inverse，所以直接执行一式也就 $O(\sqrt{V})$ 轮.
如果 $y-1\gt \sqrt{V}$ ，那么 $\text{floor}(\frac{p'-1}{y-1})$ 最多 $O(\sqrt{p})$ 个值. 我们对于每一次步长 $\text{floor}(\frac{p'-1}{y-1})$ 计算需要加多少次.

需要注意的是，有可能 $\text{floor}(\frac{p'-1}{y-1})=0$ ，这个时候需要及时退出. 时间复杂度 $O(\sqrt{V})$

AC Code

#include <bits/stdc++.h>
using ll = long long;
constexpr ll N = 1e12, sk = 1e6;

ll x, y, k;

void run() {
    std::cin >> x >> y >> k;
    if (y == 1) return std::cout << "-1\n", void();

    auto find = [&] {
        ll f = (k - 1) / (y - 1);
        return (f + 1) * (y - 1) - 1;
    };

    for (; x > 0;) {
        ll r = find();
        ll step = (k - 1) / (y - 1);
        if (step == 0) break;

        ll d = (r - k + 1) / step + 1;
        d = std::min(d, x);
        k = k + step * d;
        x -= d;

        if (k > N) return std::cout << "-1\n", void();
    }
    std::cout << k << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

Educational Codeforces Round 184 (Rated for Div. 2)

A - Alice and Bob

D2 - Removal of a Sequence (Hard Version)

E-