题解：B4395 [常州市赛 2025] 金币

· · 题解

题目分析

由题意可知，答案一定对应某一轮中的第一个位置。逆向考虑，第一个位置对应前一轮中的第二个位置，前一轮中的第二个位置又对应前前一轮中的某一个位置，……。我们可以写出一个数列的递推式：

\begin{aligned}a_1&=1,\\a_{i+1}&=f(a_i)\end{aligned}

其中，a_i 表示答案对应倒数第 i 轮中的位置，f(n) 是一个函数。观察从一轮到另一轮的过程：

\begin{alignat*}{5}\textcolor{red}1,\,&2,\dots,~~~~~~~k,\,&&\textcolor{red}{k+1},\,&&k+2,&&\dots,~~~~~~~2k,&&\dots\\&1,\dots,k-1,&&&&~~~~~~~k,&&\dots,2k-2,&&\dots\end{alignat*}

容易看出，f(n)=n+\left\lceil\frac n{k-1}\right\rceil，故 a_{i+1}=a_i+\left\lceil\frac{a_i}{k-1}\right\rceil。于是，我们可以递推得到数列 \{a_i\} 的每一项，答案就是数列 \{a_i\} 中不大于 n 的最大值。这样不能通过本题，例如 n={10}^{12},k=5\times{10}^{11} 这组数据需要计算到下标 7.5\times{10}^{11}，才能得出答案。

考虑优化，我们将数列 \{a_i\} 根据 \left\lceil\frac{a_i}{k-1}\right\rceil 分块（不是数据结构中的分块）。这样做的原因是在每一块内，数列 \{a_i\} 是一个等差数列，容易查询不大于 n 的最大值，以及跳到下一块。具体地，设等差数列首项为 m，公差为 t=\left\lceil\frac m{k-1}\right\rceil，查询不大于 n 的最大值的过程：

\begin{aligned}&m+it\le n\\\Rightarrow~&i_{\max}=\left\lfloor\frac{n-m}t\right\rfloor\\\Rightarrow~&(m+it)_{\max}=m+\left\lfloor\frac{n-m}t\right\rfloor t\end{aligned}

跳到下一块的过程：

\begin{aligned}&\left\lceil\frac{m+it}{k-1}\right\rceil>t\\\Rightarrow~&m+it>t(k-1)\\\Rightarrow~&i_{\min}=\left\lfloor\frac{tk-m}t\right\rfloor\\\Rightarrow~&(m+it)_{\min}=m+\left\lfloor\frac{tk-m}t\right\rfloor t\end{aligned}

当 m>n 时，循环无意义，可以退出。每次循环 t 至少增加 1，故第 i 次循环时 t\ge i。每次循环 m 至少增加 t，故第 i 次循环时 m\ge1+2+\cdots+i=\frac{i(i+1)}2，循环次数不大于 \sqrt{2n}，可以通过本题。

AC Code

#include<iostream>
using namespace std;
long long n,k,m=1,ans;
int main(){
    cin>>n>>k;
    while(m<=n){
        long long t=(m-1)/(k-1)+1;//ceil的计算技巧，分子减一，外面加一
        long long nxt=m+(t*k-m)/t*t,mx=m+(n-m)/t*t;
        if(mx<nxt)ans=mx;//如果没有if，答案会偏大
        m=nxt;
    }
    cout<<ans;
}