D2. Removal of a Sequence (Hard Version)

时间限制：每测试点 2 秒内存限制：512 MB

问题描述

这是本题的困难版本。两个版本之间的区别在于对 $x$ 的限制：在这个版本中， $x \le 10^{12}$ 。

Polycarp 有一个包含所有从 $1$ 到 $10^{12}$ 的自然数的序列。他决定通过执行以下操作 $x$ 次来修改这个序列：

每次同时移除所有在位置 $y$ , $2 \cdot y$ , $3 \cdot y$ , ..., $m \cdot y \le n$ 的数字，其中 $n$ 是当前序列的长度。

之后，Polycarp 想要找出剩余序列中第 $k$ 个数字，或者确定结果序列的长度小于 $k$ 。

请帮助 Polycarp 解决这个问题！

考虑一个例子。设 $x=2$ , $y=3$ , $k=5$ ，那么：

[此处原题有图示，示意删除过程]

用红线划掉的数字在第一次操作后被移除，用蓝线划掉的数字在第二次操作后被移除。因此，位置 $k=5$ 的数字是数字 $10$ 。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10$ )。接下来是每个测试用例的描述。

每个测试用例只有一行，包含三个整数 $x$ , $y$ , $k$ ( $1 \le x,y,k \le 10^{12}$ )。

输出格式

对于每个测试用例，输出结果序列中第 $k$ 个位置的正整数，或者如果结果序列的长度小于 $k$ ，则输出 $-1$ 。

样例输入

6
2 3 5
2 5 1
20 2 1000000000000
175 10 28
1000000000 998244353 1999999999
1 1 1

样例输出

你说的完全正确。昨天的 D1 版本， $x$ 很小（ $x \le 100$ ），所以你那个循环 $x$ 次的模拟解法可以通过。

但今天的 D2 版本， $x$ 高达 $10^{12}$ ，while(x--) 循环 $10^{12}$ 次一定会 TLE（超时）。

我们需要一种更快的方法来计算 $x$ 次操作。

核心问题分析

你的 D1 代码逻辑是正确的：它在“反向”模拟这个过程。

一次操作的正向： new_pos = old_pos - floor(old_pos / y)。
一次操作的反向：给你新位置 k，找到旧位置 p。

你推导出的公式 p = k + (k - 1) / (y - 1) 是完全正确的。它计算的是：操作 1 次后，位于第 k 位的数，在操作前的原始位置 p 是多少。

D1 和 D2 的任务都是计算这个函数的 $x$ 次迭代：

$f(p) = p + \lfloor (p - 1) / (y - 1) \rfloor$

我们要计算 $p_{final} = f(f(f(...f(k)...)))$ (总共 $x$ 次)。

D2 的解法：“加速模拟” / “分块跳跃”

我们不能循环 $x$ 次，但我们可以观察 $f(p)$ 的行为。

$p_{new} = p + \Delta$

其中，增量 $\Delta = \lfloor (p - 1) / (y - 1) \rfloor$ 。

关键在于： $\Delta$ 的值并不会在每一步都改变！

$p$ 在增加， $\Delta$ 也会随之增加。但 $\Delta$ 会在某一个值上“停留”很多步，直到 $p$ 增长到一定程度， $\Delta$ 才会 +1 (或更多)。

我们的策略是：

计算当前 $p$ 对应的增量 $\Delta$ 。
计算出这个 $\Delta$ 值能持续多少步（设为 s 步），才会导致 $\Delta$ 发生改变。
我们有 x 步要走，有 s 步可以保持 $\Delta$ 不变。
- 取 steps_to_take = min(s, x)。
- 我们一次性“跳”过这 steps_to_take 步。
- p = p + steps_to_take * delta
- x = x - steps_to_take
重复这个过程，直到 x = 0 或者 $p$ 超过了 $10^{12}$ 。

如何计算 s？

$\Delta$ 发生改变的临界点是 $(p - 1) / (y - 1)$ 跨越了一个新的整数。

当前的 $\Delta = \lfloor (p - 1) / (y - 1) \rfloor$ 。

下一个 $\Delta' = \Delta + 1$ 。

我们需要找到多少步 s 之后， $p_{new} = p + s \cdot \Delta$ ，使得 $\lfloor (p_{new} - 1) / (y - 1) \rfloor \ge \Delta + 1$ 。

即 $\lfloor (p + s \cdot \Delta - 1) / (y - 1) \rfloor \ge \Delta + 1$ 。

这意味着 $(p + s \cdot \Delta - 1) \ge (\Delta + 1) \cdot (y - 1)$ 。

解出 $s$ ：

$s \cdot \Delta \ge (\Delta + 1)(y - 1) - p + 1$

num_needed = (delta + 1) * (y - 1) - p + 1

s = ceil(num_needed / delta)

s = (num_needed + delta - 1) / delta (C++ 整数除法)

这个 s 就是 $\Delta$ 改变之前我们最多能走的步数。

因为 $\Delta$ (和 $p$ ) 几乎是指数级增长的，所以 $\Delta$ 改变的次数非常少（大约 $O(\log N)$ 级别），总复杂度非常快。

修正后的代码

这是你的代码的 D2 版本，应用了“分块跳跃”的加速模拟。

C++

/*
Problem: CF 2169 D2 (Hard Version)
Logic: Fast-forwarding / Block-jumping simulation
We need to compute f(f(...f(k)...)) x times, where f(p) = p + (p-1)/(y-1).
The D1 solution times out because x is 10^12.
The D2 solution notices that the increment delta = (p-1)/(y-1) stays constant
for multiple steps. We calculate how many steps 's' delta remains constant,
and then jump 'min(s, x)' steps at once.
*/


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
// N 是题中给定的原始序列最大长度
const LL N=1000000000000, INF=0x3f3f3f3f;


void solve() {
    LL x,y,k;
    cin>>x>>y>>k;

    // y=1 时，第一次操作就会移除 1, 2, 3... 所有数，序列变空。
    if(y == 1) {
        printf("-1\n");
        return;
    }

    LL p = k; // p 是我们当前的值，从 k 开始

    // 循环，直到 x 次操作全部用完
    while(x > 0) {
        // 如果 p 已经超过了 N，说明最终的 k 无法达到
        if (p > N) break;

        // 计算增量 delta
        LL delta = (p - 1) / (y - 1);

        // 如果 delta == 0，意味着 p < y
        // f(p) = p + 0 = p。p 不会再增长了。
        // 我们可以直接跳出循环。
        if (delta == 0) {
            break;
        }

        // --- D2 核心：计算能跳多少步 ---
        // 我们要找到最小的 s，使得 (p + s*delta - 1) / (y - 1) > delta
        // 临界值是 (delta + 1) * (y - 1)
        // 我们需要 p + s*delta - 1 >= (delta + 1) * (y - 1)
        // s*delta >= (delta + 1)*(y - 1) - p + 1
        LL num_needed = (delta + 1) * (y - 1) - p + 1;

        // s = ceil(num_needed / delta)
        // 用整数除法实现: s = (num_needed + delta - 1) / delta
        LL s = (num_needed + delta - 1) / delta;

        // s 是 delta 改变前可以走的最大步数
        // x 是我们剩下的步数
        // 我们实际能走的步数是二者的最小值
        LL steps_to_take = min(s, x);

        // --- 安全性检查：防止 p + steps * delta 溢出 ---
        // 我们要计算 p + steps_to_take * delta
        // 检查 p + add > N 是否等价于 add > N - p
        // 以及 add (即 steps*delta) 本身是否溢出
        // 检查 (N - p) / delta < steps_to_take
        if (delta > 0 && steps_to_take > (N - p) / delta) {
            // 这次跳跃会超过 N
            p = N + 1; // 标记为溢出
            break;     // 退出循环
        }

        // --- 执行跳跃 ---
        p = p + steps_to_take * delta;
        x = x - steps_to_take;
    }

    // 循环结束，检查最终结果
    if(p > N) {
        printf("-1\n");
    } else {
        printf("%lld\n", p);
    }

    return;
}

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