Edu-CF-184-D1. Removal of a Sequence (Easy Version)（把找到剩余的第 k 个数字，转化为找到一个长度为 len 的初始序列，使得其剩余至少 k 个数字。） · znzryb
## 题目大意
**这是问题的简单版本。版本之间的区别在于**$x$**的约束；在这个版本中，**$x \le 10^5$**。**
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 $。
## 思路讲解
二分答案。
思路参考了[A_G 的代码](https://codeforces.com/contest/2169/submission/349170159)。
将这道题目转化为二分答案的关键，就在于**把找到剩余的第** $ k $ **个数字，转化为找到一个长度为** $len$ **的初始序列，使得其剩余至少** $k$ **个数字**，那么不难发现，最小的，符合我们的要求的 $len$ 就是答案。
那么，一次操作会减少多少个数字（长度为 $len$ 时）？ 其实就是 $\lfloor \frac{len}{y}\rfloor$。
因此，简单版本，检查函数也不难书写，直接模拟改过程即可：
```cpp
auto check=[&](ll len) {
ll cnt=1;
while (cnt<=X) {
if (len<=0) {
break;
}
len-=len/Y;
++cnt;
}
if (len>=K) {
return true;
}
return false;
};
```
## AC代码
AC
[https://codeforces.com/contest/2169/submission/360432707](https://codeforces.com/contest/2169/submission/360432707)
::: 源代码
```cpp
/**
* Problem: D1. Removal of a Sequence (Easy Version)
* Contest: Educational Codeforces Round 184 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2169/problem/D1
* Created: 2026-01-29 12:53:23
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
void Solve() {
ll X,Y,K;
// X 是删除次数，Y 是删除参数，K 是查询的位置
cin >> X >> Y >> K;
if (Y==1) {
cout<<-1<<"\n";
return;
}
auto check=[&](ll len) {
ll cnt=1;
while (cnt<=X) {
if (len<=0) {
break;
}
len-=len/Y;
++cnt;
}
if (len>=K) {
return true;
}
return false;
};
auto range=ranges::views::iota(1ll,(ll)1e12+1)|views::reverse;
auto it=ranges::partition_point(range,check);
if (it==range.begin()) {
cout<<-1<<"\n";
return;
}
ll ans=*ranges::prev(it);
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2169/submission/360432707
*/
```
:::
## 心路历程（WA，TLE，MLE……）