题解 | # D. Removal of a Sequence #

$[因吹斯汀结论]$

结论：设之前的位置为 $pre\_pos$ ，然后删除位置坐标为 $y$ 的倍数的数，那么原来第 $pre\_pos$ 个数的位置变为： $now\_pos = pre\_pos - \lfloor \frac{pre\_pos}{y} \rfloor$

$\lfloor \frac{pre\_pos}{y} \rfloor$ 的意思是 $[1,pre\_pos]$ 有多少个 $y$ 的倍数，所以直接减去 $\lfloor \frac{pre\_pos}{y} \rfloor$

$now\_pos = pre\_pos - \lfloor \frac{pre\_pos}{y} \rfloor$ 变形可以得到 $pre\_pos = now\_pos + \lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ ，意思是之前的位置等于现在的位置加上删除数字的个数

删除数字的个数等于 $\lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ ，为什么是 $now\_pos -1$ ，因为如果 $now\_pos -1$ ，则算出来的 $pre\_pos$ 一定不是 $y$ 的倍数，否则有可能是 $y$ 的倍数

故可以 $O(x)$ 时间复杂度一步步算出 $pre\_pos$ :

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){

    int x, y, k; cin >> x >> y >> k;
    if(y == 1){
        cout << "-1" << endl;
        return ;
    }
    for(int i = 1; i <= x; i ++){
        k = k + (k - 1) / (y - 1);
        if(k > 1000000000000){
            cout << "-1" << endl;
            return ;
        }
    }
    cout << k << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}

也可以用二分来做：上面的代码用的是 $pre\_pos = now\_pos + \lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ ，可以 $O(x)$ 时间复杂度一步步算出 $pre\_pos$ 。那也可以用 $now\_pos = pre\_pos - \lfloor \frac{pre\_pos}{y} \rfloor$ ，因为满足单调性：

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;



int x, y, k;

bool check(int pos){
    for(int i = 1; i <= x; i ++) pos -= pos / y;
    if(pos >= k) return true;
    else return false;
}
void solve(){

    cin >> x >> y >> k;
    int l = 1, r = 1000000000000, ans = -1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}

第一段代码的时间复杂度为 $O(x)$ ，第二段代码的时间复杂度为 $O(40\times x)$ ，在 $x \leq 10^{5}$ 条件下都能通过

困难版本则是将 $x$ 的范围提升至 $10^{12}$ 次方

$pre\_pos = now\_pos + \lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ ，这个公式原来是一次次推 $pre\_pos$ ，所以时间复杂度为 $O(x)$ 。但是累加的 $\lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ 可能值相同，导致多次执行加上相同的数字，不如直接求次数 $cnt$ ，直接累加上 $cnt \times \lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ ，这样大大减少了时间复杂度

那么需要保证从 $now\_pos$ 开始累加了 $cnt$ 次 $\lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ 后， $\lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ 才会发生变化，所以 $now\_pos$ 累加了 $cnt - 1$ 次后的 $\lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ 仍然与一开始的 $\lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ 值相同，所以有：

首先令 $t = \lfloor \frac{now\_pos - 1}{y- 1} \rfloor$ ，则 $\frac{pre\_pos + (cnt - 1) \times t - 1}{y - 1} < t + 1$

公式的计算.....

$pre\_pos + (cnt - 1) \times t - 1 < (t + 1) \times (y - 1)$

$pre\_pos + (cnt - 1) \times t < (t + 1) \times (y - 1) + 1$

因为 $pre\_pos + (cnt - 1) \times t$ 是整数，所以 $pre\_pos + (cnt - 1) \times t \leq (t + 1) \times (y - 1)$

解得 $cnt \leq \lfloor \frac{(t + 1) \times (y - 1) - pre\_pos + t}{t} \rfloor$ ，所以 $cnt$ 的最大值就为 $\lfloor \frac{(t + 1) \times (y - 1) - pre\_pos + t}{t} \rfloor$

核心代码：

如果 $t = 0$ 了，那么无论加多少次，都灭有变化，进入死循环，所以 $break$ 推出

$cnt$ 累加的次数不能超过 $x$ ，所以得与 $x$ 取最小值

如果 $cnt = 0$ ，表示到达下一次的边界情况，仍然会死循环，所以设置 $cnt = 1$ ，让其至少操作 $1$ 次

然后 $k$ 位置累加， $x$ 减去操作次数

while(x > 0){
    int t = (k - 1) / (y - 1);
    if(t == 0) break;
    int cnt = ((t + 1) * (y - 1) - k + t) / t;
    cnt = min(cnt, x);
    if(cnt == 0) cnt = 1;
    k += cnt * t;
    x -= cnt;
    if(k > 1000000000000){
        cout << "-1" << endl;
        return ;
    }
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){

    int x, y, k; cin >> x >> y >> k;
    if(y == 1){
        cout << "-1" << endl;
        return ;
    }
    while(x > 0){
        int t = (k - 1) / (y - 1);
        if(t == 0) break;
        int cnt = ((t + 1) * (y - 1) - k + t) / t;
        cnt = min(cnt, x);
        if(cnt == 0) cnt = 1;
        k += cnt * t;
        x -= cnt;
        if(k > 1000000000000){
            cout << "-1" << endl;
            return ;
        }
    }
    if(k > 1000000000000) cout << "-1" << endl;
    else cout << k << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}