CF1242D Number Discovery
临题解涕零，不知所言。
若一个数是以和的形式加入的，称这样的数为 non-self 数。
显而易见，若将每 \(k+1\) 个数分段，则每段至多有一个 non-self 数，但是这个结论是非常 weak 的，因为大多数段不含有 non-self 数。然而，这启发我们取一个合理的段长，然后计算 \(n\) 所在段内信息。
考虑怎么算答案，显然，可以利用 \(n\) 减去序列中 non-self 数的数量再加上比 \(n\) 小的 non-self 数数量。
所以，如果能有一个段长，使得每段内有且仅有一个 non-self 数那么就容易计算答案了。
这时，你点开题解，获得一个重要结论。
取段长为 \(k^2 + 1\)，则每段内恰有一个 non-self 数。
考虑归纳证明。不难发现，第 \(i\) 段会对后面 \(k\) 段确定一个 non-self 数，任务是证明这些段不重不漏地覆盖了第 \([ik + 1, ik + k]\) 段。
假设已知第 \(i\) 段中的 non-self 数为 \(x\)。那么可以求出第 \((ik + t + 1)\) 个的 non-self 数
\[\sum_{j = 1} ^ k {(i (k^2 + 1) + tk + j)} + offset = (ik + t) (k ^ 2 + 1) + \frac{k(k + 1)}{2} - t + offset \]其中 \(offset\) 表示由于 non-self 产生偏差的贡献。不难发现这个数一定落在第 \((ik + t + 1)\) 段内。
对于 \(offset\)，有
\[offset = \sum_{j=1}^k {[i (k ^ 2 + 1) + tk + j \ge x]} = \max(0, \min(k - (x - (i(k ^ 2 + 1) + tk)) + 1)) \]所以可以通过递归求出 \(n\) 所在段的 non-self 数，然后 \(O(\log n)\) 处理询问。
#include <cstdio>
#include <iostream>
using namespace std;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
typedef long long LL;
LL n;
LL k, B;
LL offset;
LL find(LL id) {
if(!id) return k * (k + 1) / 2;
LL i = id / k, t = id - i * k - 1, x = find(i);
LL offset = max((LL)0, min(k, k - (x - (i * B + (t + 1) * k)) + 1));
LL tx = (i * k + t + 1) * B - 1 + k * (k + 1) / 2 - t + offset;
return tx;
}
void solve() {
read(n), read(k);
B = k * k + 1;
LL id = (n - 1) / B;
LL x = find(id);
if(n == x) printf("%lld\n",(id + 1) * (k + 1));
else {
LL pre = id + (n > x);
LL tot = (n - 1 - pre) / k;
printf("%lld\n",n - pre + tot);
}
}
int main() {
int T; read(T);
while(T--) solve();
}