[[二分]] [[数学]] [[逆向思维]]

D1. Removal of a Sequences (Easy Version)

时间限制：每个测试 2 秒 内存限制：每个测试 512 兆字节

问题描述

这是问题的简单版本。两个版本的区别在于 $x$ 的约束不同；在这个版本中，$x \le 10^5$。

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

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

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

请帮助 Polycarp 解决这个问题！

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

![[Pasted image 20251114235554.png]]

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

输入格式

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

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

输出格式

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

样例输入

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

样例输出

10
1
-1
2339030304
2000199999
-1

根据AI 思路写的代码

// Problem: CF 2169 D1
// Contest: Codeforces - Educational Codeforces Round 184 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2169/problem/D1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=1e12,INF=0x3f3f3f3f;


void solve() {
    LL x,y,k;
    cin>>x>>y>>k;
    if(y==1) printf("-1\n");
    else{
        LL p=k+(k-1)/(y-1);
        x-=1;
        while(x--){
            if(p>N){
                printf("-1\n");
                return ;
            }
            k=p;
            p=k+(k-1)/(y-1);
        }
        printf("%lld\n",p);
    }


    return;
}

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

现在我们把所有逻辑拼起来：

1. 特殊情况：如果 $y = 1$，序列会立刻变空。我们应该怎么做？

2. 一般情况 ($y \ge 2$)：

   • 我们有一个目标位置 $k$ 和操作次数 $x$。

   • 我们有一个“撤销”公式：$p = f(k) = k + \lfloor (k-1) / (y-1) \rfloor$。

   • 我们要“循环套用”这个公式 $x$ 次。

   • 在每次套用公式时，我们都要检查新算出来的 $p$ 是否超过了 $10^{12}$。如果超过了，说明什么？

   • 如果循环 $x$ 次都没有超过 $10^{12}$，那么最后得到的 $p$ 是什么？

你能把这几个点串起来，形成一个完整的算法流程吗？

对题目思考历程

当然！把我们一起探索的过程整理成笔记是个非常好的复习方法。

这是我们解题思路的“学习历程”：

1. 问题的起点：正向模拟（困难）

• 我们的目标：在 $x$ 次操作后，找到第 $k$ 个剩下的数。

• 最初的直觉：你最开始的想法是“正向”模拟。

• 你发现的规律：

  • 前 $y-1$ 个数永远不动。

  • 可以按“每 $y$ 个一块”来思考。

• 遇到的困难：我们都同意，这种“正向”方法非常复杂。因为序列在不断“压缩”，一个数的位置在每次操作后都会变，很难追踪。

2. 关键转折：倒着推

• 我们的“Aha!”时刻：我们决定不从 $S_0 \to S_x$ 正向推，而是从 $S_x \to S_0$ 倒着推。

• 核心问题：如果一个数最终在 $S_x$ 的第 $k$ 位，那么它在 $S_{x-1}$ 的第几位？... 最终，它在 $S_0$（原始序列）的第几位？

3. 核心武器：“单步撤销”公式

• 我们推导了一次操作的“撤销”公式：

  • 假设 $y \ge 2$。

  • 如果一个数在操作_后_的位置是 $k$。

  • 那么它在操作前的位置 $p$ 就是：

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

• 这个公式的意义：它告诉我们，操作前的 $p$ 等于操作后的 $k$，再加上“在它前面被移除的数的个数”（即 $\lfloor (k-1) / (y-1) \rfloor$）。

4. 形成算法：循环套用

• 你的想法：你马上想到了，我们只需要“循环套用”这个公式 $x$ 次。

• 算法流程：

  1. 我们从 $k_{final} = k$ 开始。

  2. 我们循环 $x$ 次，每次都用“撤销”公式来更新 $k$：

     k_prev = k_current + floor((k_current - 1) / (y - 1))

  3. 循环 $x$ 次后，我们得到的那个 $p$ 值（也就是最后的 k_prev），就是它在 $S_0$ 里的原始位置。

  4. 因为 $S_0$ 就是 $1, 2, 3, \dots$，所以原始位置 $p$ 上的数就是 $p$ 本身。

5. 处理边界：-1 的情况

我们一起找到了两种导致 "-1" 的情况：

1. $y = 1$：你一眼就看出来了。如果 $y=1$，第一次操作就会移除所有数，序列变空，所以直接输出 -1。

2. $p$ "太大"：

   • 你意识到如果 $p$ 变得“很大”，就说明“不行了”。

   • 我们一起明确了这个“很大”的界限：原始序列只有 $1$ 到 $10^{12}$。

   • 结论：在 $x$ 次“撤销”的计算过程中，任何一步算出来的 $p$（或 $k_{current}$）如果超过了 $10^{12}$，就说明我们找的这个数来自 $10^{12}$ 之外，这不可能。我们应立刻停止，输出 -1。

6. 代码实现与调试

• 最后，你把这个逻辑写成了代码。

• 我们发现了第一个小 bug：在 C++ 中，const int N=1e12 会导致溢出和错误，因为 $10^{12}$ 远超 int 范围，应该用 long long 来定义。

这个笔记总结了我们从卡住到找到思路、再到完善算法的全过程！

公式推导部分

没问题！你希望把思路笔记的第三部分写得更详细，我们来专注完善这部分的推导。

这是你笔记的更新版本，只扩展了第 3 节：

---

3. 核心武器：“单步撤销”公式 (详细推导)

在这一步，我们的目标是推导出：已知操作后的位置 $k$，如何求出操作前的原始位置 $p$。

步骤 1：建立“正向”和“反向”关系

• 正向关系：我们先看一次操作。如果一个数在 $S_0$（原始序列）中的位置是 $p$，并且它没有被移除（即 $p$ 不是 $y$ 的倍数），那么它在 $S_1$（新序列）中的位置 $k$ 是多少？

  • 在 $p$ 前面（包括 $p$ 自身），总共有 $\lfloor p/y \rfloor$ 个数被移除了。

  • 所以，它的新位置 $k = p - \lfloor p/y \rfloor$。

• 反向问题 (我们的目标)：我们知道了 $S_1$ 中的位置 $k$，想反解出 $S_0$ 中的位置 $p$。

  • 我们把上面的公式重新排列：

    $$p = k + \lfloor p/y \rfloor$$

  • 这个公式看起来很棘手，因为 $p$ 出现在了等号的两边，而且一边还在 floor 函数里。

步骤 2：分析“添加”与“保留”的关系

我们换个角度看 $p = k + \lfloor p/y \rfloor$ 这个式子：

• $p$ 是“原始位置”。

• $k$ 是“保留下的数的位置”。

• $m = \lfloor p/y \rfloor$ 是“被移除的数的个数”。

所以 $p = k + m$，即 原始位置 = 保留数 + 移除数。我们的目标变成了：如何只用 $k$ 来表示 $m$？

• 关键洞察（块的比例）：

  • 在 $S_0$ 中，每 $y$ 个数（一个“块”），比如 $\{1, 2, \dots, y\}$。

  • 操作后，有 $y-1$ 个数被保留（$\{1, 2, \dots, y-1\}$）。

  • 有 $1$ 个数被移除（$\{y\}$）。

• 推论：这个“保留 : 移除”的比例 $(y-1) : 1$ 是恒定的。

• 这意味着，我们每数 $y-1$ 个“保留数”，就一定对应着 $1$ 个“移除数”被我们跳过了。

步骤 3：从“比例”到“公式”

我们要计算 $m$（移除数）和 $k$（保留数）的关系。

• 根据 $(y-1) : 1$ 的比例， $m$ 应该约等于 $k / (y-1)$。

• 但我们需要一个精确的整数公式，而不是近似。

• 我们来测试一下：

  • 当 $k = 1, \dots, y-2$ 时，我们还在第一个块里， $m$ 应该是 $0$。

  • 当 $k = y-1$ 时（这是 $S_0$ 中的 $y-1$）， $m$ 仍然是 $0$。

  • 当 $k = y$ 时（这是 $S_0$ 中的 $y+1$），我们刚刚跨过了第一个被移除的数 ($y$)。所以 $m$ 应该等于 $1$。

• 我们想找一个 $m$ 的公式，它在 $k=1$ 到 $k=y-1$ 时都等于 $0$，但在 $k=y$ 时要等于 $1$。

• 测试公式 1：$m = \lfloor k / (y-1) \rfloor$

  • 当 $k = y-1$ 时， $m = \lfloor (y-1) / (y-1) \rfloor = 1$。

  • 这不对！$k=y-1$ 时 $m$ 应该是 $0$。我们“加 1”加得太早了。

• 测试公式 2：$m = \lfloor (k-1) / (y-1) \rfloor$

  • 当 $k = 1$ 时， $m = \lfloor (1-1) / (y-1) \rfloor = \lfloor 0 \rfloor = 0$。（正确）

  • 当 $k = y-1$ 时， $m = \lfloor ((y-1)-1) / (y-1) \rfloor = \lfloor (y-2) / (y-1) \rfloor = 0$。（正确）

  • 当 $k = y$ 时， $m = \lfloor (y-1) / (y-1) \rfloor = \lfloor 1 \rfloor = 1$。（正确）

• 这个公式 $m = \lfloor (k-1) / (y-1) \rfloor$ 完美地捕捉了“每数完 $y-1$ 个保留数后，才增加 1 个移除数”的行为。

步骤 4：最终推导

1. 我们的目标是求 $p$。

2. 我们知道 $p = k + m$ (原始 = 保留 + 移除)。

3. 我们刚推导出，移除数 $m$ 可以由保留数 $k$ 精确计算：$m = \lfloor (k-1) / (y-1) \rfloor$ (假设 $y \ge 2$ )。

4. 把 $m$ 替换掉：

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

这就是我们“单步撤销”的核心公式。

CF 题解思路

• 在许多需要找到第 $k$ 个元素的问题中，会出现二分查找。让我们试着在这个问题的答案上也应用二分搜索。我们只需要了解检查函数的外观。让我们确定一个数字 $p$ ，

我们想知道如果初始序列由 $1$ 到 $1$ 的所有自然数组成，那么最终会剩下多少个数 $p$ .由于在每个动作中PolyCarp移除索引是 $y$ 的倍数的序列的所有元素，可以使用公式 $\lfloor\frac{p}{y}\rfloor$ 计算一个操作后删除的元素数。问题的简单版本中的约束允许我们计算Polycarp的每个动作之后的剩余序列的长度，因此，结果序列的长度可以计算如下：

如果我们找到这样一个最大值 $p$ ，在Polycarp的所有动作之后

如果有 $k$ 个元素，那么这个 $p$ 就是答案。不难证明我们的函数是单调的，因此我们可以理直气壮地使用二分搜索。

渐近时间复杂度： $O(x \log A)$ ，其中 $A$ 依赖于初始序列的长度，在这个问题中 $A = 10^{12}$ 。

CF 题解代码

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1000000000000LL + 1;

void solve(){
    int x;
    long long y, k;

    cin >> x >> y >> k;

    long long l = 1, r = INF;
    long long m;

    while(l <= r){
        m = l + (r - l) / 2;
        long long ost = (m - 1);
        for (int i = 0; i < x; i++){
            ost -= ost / y;
        }
        if (ost + 1 > k){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }

    if (r == INF){
        cout << -1 << '\n';
    }
    else{
        cout << r << '\n';
    }
}

signed main()
{
#ifdef FELIX
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int t = 1;
  cin >> t;
  while(t--){
    solve();
  }

#ifdef FELIX
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    chrono::high_resolution_clock::now()
      - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

二分思路

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=2e12;

void solve(){
    LL x,y,k;
    cin>>x>>y>>k;
    if(y==1) printf("-1\n");
    else{
        LL l=1,r=INF;
        while(l<r){
            LL mid=l+r>>1;
            LL ans=mid;
            for(int i=0;i<x;i++){
                ans-=ans/y;
            }
            if(ans>=k) r=mid;
            else l=mid+1;
        }

        if(r==INF||r>1e12) printf("-1\n");
        else printf("%lld\n",l);
    }

    return ;
}

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

check 函数的意义

操作 $x$ 次后，从 $1$ 到 $10^{12}$ 的序列中，哪些数字被保留，哪些数字被移除，这个最终的“保留集合”是完全固定不变的。

那么，为什么题解里的“二分答案”法要用一个猜的 $p$ (代码里的 m) 来模拟呢？

关键点：操作的独立性

这个二分法利用了一个非常巧妙的特性：一个数 $p$ 的“命运”（即它最终是否被保留），只取决于 $1$ 到 $p$ 之间的数，而与 $p+1$ 之后的数完全无关。

举个例子：

• 我们想知道数字 10 最终是否被保留。

• 第一次操作（$y=3$）：移除第 3, 6, 9... 个数。

  • 序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]

  • 3 (第3位) 被移除。

  • 6 (第6位) 被移除。

  • 9 (第9位) 被移除。

  • 10 的位置只受它前面 3, 6, 9 被移除的影响。它从第 10 位变成了第 $10-3 = 7$ 位。

  • 它不受 $12, 15, ...$ 等这些它后面的数被移除的影响。

• 第二次操作（$y=3$）：

  • 新序列 [1, 2, 4, 5, 7, 8, 10, ...]

  • 10 现在在第 7 位。

  • 移除新序列的第 3, 6, 9... 位。

  • 4 (第3位) 被移除。

  • 8 (第6位) 被移除。

  • 10 的位置从第 7 位变成了第 $7-2 = 5$ 位。它被保留了。

check(p) 函数的真正含义

因此，题解中的 check(p) 函数（即代码里那个 for 循环），它计算的不是一个“假设”的情景。它计算的是：

check(p) = “在那个固定的、最终的保留集合中，有多少个数是小于或等于 $p$ 的？”

因为 $p$ 的命运和 $p$ 后面的数无关，所以：

1. 我们对 [1, 2, ..., p] 这个短序列进行 $x$ 次模拟。

2. 得到的剩余数量。

3. 这个数量精确地等于我们对 [1, 2, ..., 10^12] 这个长序列进行 $x$ 次模拟后，再去数里面有多少 $\le p$ 的数。

把逻辑串起来

1. 目标： 找到最终保留集合中的第 $k$ 个数。

2. 二分： 我们猜这个数是 $p$。

3. 验证 check(p)： 我们计算一下 "最终保留集合中 $\le p$ 的数有多少个？"。

   • 如果 check(p) 算出来等于 $k$（比如 check(10) = 5），这说明在最终保留的数中，$\le 10$ 的有 5 个。

   • 我们再检查 check(p-1)（比如 check(9) = 4），这说明在最终保留的数中，$\le 9$ 的有 4 个。

4. 结论：

   • $\le 9$ 的有 4 个。

   • $\le 10$ 的有 5 个。

   • 这恰好说明，第 5 个被保留的数就是 10。

所以，你没理解错，最终的集合是固定的。二分法只是在用 check(p) 这个函数来高效地“查询”这个固定集合的“前缀和”（即 $\le p$ 的元素个数），从而定位到第 $k$ 个数。

[[二分]]

关于二分思路的总结

好的，没问题！这道题是“二分答案”的经典应用。

我把我们之前聊到的所有关于“为什么这题能用二分”的要点，为你总结成一个完整的复习笔记：

---

核心思想：二分答案 (Binary Search on Answer)

我们不是在 [1, 2, 3, ...] 这个序列上进行二分，而是在“答案”可能的范围 [1, 10^{12}] 上进行二分。

我们把问题从一个“计算题”变成了一个“判断题”：

• 原问题（难）： “第 $k$ 个数是多少？”

• 新问题（易）： “我猜答案是 $p$，你帮我看看 $p$ 这个猜测是太大了还是太小了？”

为什么这题（D1）可以用二分？

因为它完美满足了“二分答案”必须的 3 个前提条件：

1. 答案具有“单调性” (Monotonicity)

这是二分法的灵魂。我们需要定义一个 check(p) 函数，它的结果必须随着 $p$ 的增大而单调（只增不减，或只减不增）。

• check(p) 函数的定义：

  “假设初始序列只有 [1, 2, ..., p]，经过 $x$ 次移除操作后，最终会剩下多少个数？”

• 为什么它是单调的？

  check(p+1) 的结果永远不可能小于 check(p)。

  • 如果数字 p+1 最终存活：check(p+1) = check(p) + 1

  • 如果数字 p+1 最终被移除：check(p+1) = check(p)

    在任何情况下，check(p) 的结果（剩余数量）都随着 $p$ 的增大而“只增不减”。这构成了完美的单调性，是可以使用二分的基础。

2. 答案具有“有界性” (Boundedness)

答案（也就是第 $k$ 个数）一定在一个已知的范围内。

• 下界 (l)： 最小是 1。

• 上界 (r)： 最大不会超过 10^{12}（甚至可以开到 2e12 来确保安全）。

[l, r] 就是我们的“二分搜索空间”。

3. “验证”远比“求解”容易 (Check vs. Solve)

• 求解（难）： 直接算出第 $k$ 个数是几，我们毫无头绪。

• 验证（易）： 对于我们猜的任何一个 $p$，我们都能用那个 for 循环（模拟 $x$ 次）快速地计算出 check(p) 的值。

---

二分的关键：我们在找什么？

我们不是在找任何一个 check(p) == k 的 $p$，因为这可能是错的（比如 check(11)=6 和 check(12)=6 的例子）。

我们真正要找的是：

“满足 check(p) >= k 的最小的那个 $p$”

这个“最小的 $p$”具有最关键的含义：

1. 当 $p$ 是这个“最小 $p$”时 (比如 $p=11$, $k=6$)

   • check(p-1) 一定 < k (例如 check(10) = 5)

   • check(p) 一定 $\ge k$ (例如 check(11) = 6)

   • check 的结果在 $p$ 这里发生了“跳跃”（从 5 蹦到了 6）。

   • 这个“+1”只能来自一个地方：数字 $p$ 本身存活了！

   • 因此，$p$ 自己就是我们要找的第 $k$ 个存活者。

2. 当 $p$ 不是“最小 $p$”时 (比如 $p=12$, $k=6$)

   • check(p-1) 已经 $\ge k$ (例如 check(11) = 6)

   • check(p) 也 $\ge k$ (例如 check(12) = 6)

   • check 的结果在 $p$ 这里没有发生“跳跃”（从 6 保持为 6）。

   • 这个“+0”说明：数字 $p$ 本身被移除了！

   • 所以 $p=12$ 虽然满足 check(p) >= k，但它不是答案。

你的二分代码是如何实现这一点的？

你的 while(l < r) 模板正是为“寻找最小 $p$”而设计的：

C++

while(l < r){
    LL mid = l + r >> 1;
    LL ans = check(mid); // 算出 check(mid)

    if(ans >= k){
        // mid 可能是答案，但也可能是一个被删除的数 (像 p=12)
        // 我们不能停，我们必须尝试找一个更小的
        r = mid; 
    }
    else { // ans < k
        // mid 肯定不是答案，它太小了
        l = mid + 1;
    }
}
// 循环结束时，l 和 r 会在那个“最小的 p”上相遇
printf("%lld\n", l); 

这个模板会自动地帮你抛弃所有像 $p=12$ 这样的“平台点”，最终精确地停在 $p=11$ 这样的“跳跃点”上。

---

总结：什么时候用二分答案？

当你遇到一个问题（尤其是“求解第 $k$ 个...”或“最大值的最小...”）：

1. 第一反应： 我不会直接算，但如果给我一个答案 p，我能很容易地判断它（或 check(p) 的结果）是太大了还是太小了。

2. 第二反应： 这个“判断”是否具有单调性？（即，p 越大，check(p) 的结果是不是也一定越大/越小？）

3. 第三反应： 答案的范围 [l, r] 是不是确定的？

如果三条都是“是”，那么你就可以 99% 确定使用“二分答案”了。