Edu-CF-184-D2. Removal of a Sequence (Hard Version)（如何优化这个多次的向下取整触发/向下取整分数，） · 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 $。
## 思路讲解
::: D1 思路
二分答案。
思路参考了[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;
};
```
:::
---
我们直接使用这个第一问当中的这个 check 函数，由于其是 $O(X)$，会超时。我们也可以优化这个二分检查器代码，让其一次性把 $subtract\gets \lfloor \frac{len}{y}\rfloor$ 相同的一起处理。这样子，使用二分的复杂度就是 $O(\sqrt A \log A)$，其中 $\sqrt A$ 是一个数字能够拥有的这个因数数量量级。
不过题目作者专门卡了我们二分答案一手，因此必须采用逆向还原的思路。
```cpp
for (ll i=1;i<=X;++i) {
ll subtract=0;
if (len%(Y-1)==0) {
subtract=len/(Y-1)-1;
len+=subtract;
}else {
subtract=len/(Y-1);
ll dis=((Y-1)*(subtract+1))-len;
ll cnt=(dis+subtract-1)/subtract;
cnt=min(X-i+1,cnt);
i+=cnt-1;
len+=cnt*subtract;
}
if (len>(ll)1e12) {
cout<<-1<<"\n";
return;
}
}
```
逆向还原，我们知道，每出现 $y-1$ 个数字，那么就代表有一个数字被删除了，那么一次需要增长的长度就是 $\lfloor \frac{len}{y-1} \rfloor$？
这里有一个比较阴的特殊情况，就是 $len \equiv 0 \pmod {y-1}$，这个时候，能够增长的长度就是只有 $\lfloor \frac{len}{y-1} \rfloor-1$。
我们可以就像最简单的，当序列长度为 $y-1$，其达到 $y-1$ 需要多少长度，是 $y$ 吗？显然不是，其需要增长的就是 0 长度。
我们和优化二分的时候采用一样的思路，每次增长相同长度的，一起操作，这样子时间复杂度就是 $O(\sqrt A)$。
具体而言，就是先计算需要增长的长度 $subtract$，然后计算需要能够以 $subtract$ 继续增长的次数，即 $cnt$，然后 $cnt\gets \min(cnt,X-i+1)$，避免加上 $cnt$ 超过操作次数限制。不断重复这个过程，直到达到操作次数 $X$。
## AC代码
AC
[https://codeforces.com/contest/2169/submission/360686378](https://codeforces.com/contest/2169/submission/360686378)
::: 源代码
```cpp
/**
* Problem: D2. Removal of a Sequence (Hard Version)
* Contest: Educational Codeforces Round 184 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2169/problem/D2
* Created: 2026-01-29 21:32:03
* 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>
#include <cassert>
#include <cstdio>
#include <chrono>
#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;
cin >> X >> Y >> K;
// X 是删除次数，Y 是删除参数，K 是查询的位置
if (Y==1) {
cout<<-1<<"\n";
return;
}
ll len=K;
if (K<Y) {
cout<<K<<"\n";
return;
}
for (ll i=1;i<=X;++i) {
ll subtract=0;
if (len%(Y-1)==0) {
subtract=len/(Y-1)-1;
len+=subtract;
}else {
subtract=len/(Y-1);
ll dis=((Y-1)*(subtract+1))-len;
ll cnt=(dis+subtract-1)/subtract;
cnt=min(X-i+1,cnt);
#ifdef LOCAL
assert(cnt>0);
#endif
i+=cnt-1;
len+=cnt*subtract;
}
if (len>(ll)1e12) {
cout<<-1<<"\n";
return;
}
}
cout<<len<<"\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/360686378
*/
```
:::
TLE
[https://codeforces.com/contest/2169/submission/360461585](https://codeforces.com/contest/2169/submission/360461585)
::: 二分 TLE 代码
```cpp
/**
* Problem: D2. Removal of a Sequence (Hard Version)
* Contest: Educational Codeforces Round 184 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2169/problem/D2
* Created: 2026-01-29 15:52:48
* 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>
#include <cassert>
#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;
}
// X=min((ll)1e5,X);
auto check=[&](ll len) {
if (len<Y) {
if (len>=K) {
return true;
}
return false;
}
for (ll i=1;i<=X;++i){
if (len<=0) {
break;
}
// 我们去计算这个 len/Y 能除多少次，就不是 Y 了？
ll subtract=len/Y;
if (subtract<=0) {
break;
}
// 不一定所有的都是向上取整关系，比如说这道题目 rem 为 0，也是可以减 1 次。
ll rem=len-(Y*subtract-1);
ll cnt=(rem+subtract-1)/subtract;
cnt=min(X-(i-1),cnt);
#ifdef LOCAL
assert(cnt>0);
#endif
i+=cnt-1;
len-=cnt*subtract;
}
if (len>=K) {
return true;
}
return false;
};
auto range=views::iota(1ll,(ll)1e12+1ll)|views::reverse;
// #ifdef LOCAL
// debug(*range.begin());
// #endif
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;
}
/*
1
2 3 5
*/
```
:::
## 心路历程（WA，TLE，MLE……）