题意

• 定义一种操作 f(x, k) 表示把 x 在 k 操作下变为 1 的次数
• 操作有两种
  • 如果 x 当前是 k 的倍数，那么把 x 除去 k
  • 如果 x 不是 k 的倍数，那么把 x 加上 1
• 进行 T 组询问
• 每组询问给定三个参数 l, r, k 需要计算输出
  • $f(l, k) + f(l + 1, k) + \dots+ f(r, k) = \sum_{i = l}^r f(i, k)$

思考

• 对于某一个具体的数 x 和 k，计算 $f(x, k)$ 的时间是 $O(\log_k x)$
  • 这里注意，除法次数不会很多，但加法有可能达到 $k$ 或者 $x$ 的级别
  • 同时意识到，这两能取到 $10^9$，所以最终的答案可能到 $(r - l + 1)\times 10^9$，答案需要开 long long
• 所以可以很轻松的得到一个 $O(T\times (r - l + 1) \times \log _k 10^9)$ 的算法

部分分

• 对于测试点 1, 2, 4, 6（共 40 分）
  • 上面那个粗略的解法已经可以通过这 40 分
• 对于测试点 3（共 10 分）
  • 由于 k 是定值，所以只需要额外关注 x
  • 注意到 r 不超过 $2\times 10^7$
  • 所以可以预处理出 $f(1, 3), f(2, 3), \dots, f(2\times 10^7, 3)$
    • 这里要递推求
  • 对这个东西求前缀和，最后做区间查询即可
• 对于测试点 5（共 5 分）
  • 注意到 k 取了最大值
  • 那么任意的 $f(x, k)$ 其操作流程均为变到 $10^9$ 后一步到位变成 1
    • 注意 1 和 $10^9$ 特殊
  • 那么答案即为 区间长度 * 1e9 + 区间长度 - 区间 [l, r] 的总和

题解

• 记 $ask(x, k)$ 表示将 x 在除 k 意义下变为 1 的最小次数
• 记 $qur(1, len, x)$ 表示将区间 $[1, len]$ 的所有元素均在除 k 意义下变为 1 的最小次数求出来然后求和的结果
• 那么对于单次询问的 l, r, k 其答案 $ans = qur(1, r, k) - qur(1, l - 1, k)$
  • 问题落在了如何编写 $qur$ 函数上
• 其实能够发现，整个问题呈现极强的块状性
  • 以求解 $qur(1, 38, 5)$ 为例
  • 我们会发现，第一步（统筹看每个数的第一步）
  • [1, 5] 都是变成 5 再除 5，共增加了 4 + 3 + 2 + 1 + 0 - 4 = 10 - 4 = 10 - (k - 1) 次
    • 问题变成了 5 个 5 变成 1 的最小次数，也就是 5 个 1 变成 1 的次数 + 5
  • [6, 10] 变成 10 再除 5，共增加了 4 + 3 + 2 + 1 + 0 = 10 次
    • 问题变成了 5 个 10 变成 1 的最小次数，也就是 5 个 2 变成 1 的次数 + 5
  • [11, 15] 变成 15 再除 5，共增加了 10 次
    • 问题变成了 5 个 15 变成 1 的最小次数，也就是 5 个 3 变成 1 的次数 + 5
  • 。。。
  • [31, 35] 变成 35 再除 5，共增加了 10 次
    • 问题变成了 5 个 35 变成 1 的最小次数，也就是 5 个 7 变成 1 的次数 + 5
  • [36, 38] 变成 40 再除 5，共增加了 4 + 3 + 2 + 1 + 0 - 1 - 0 = 10 - 1 = 10 - 1 次
• 也就是说，对于 $qur(1, len, k)$ 其求解方式为：
  • 第一部分：[1, k]
  • 第二部分：[k + 1, 2k], [2k + 1, 3k], ..., [(d - 1)k + 1, dk]
    • 第一二部分合并
    • ans = (0 + k - 1) * k / 2 * d + dk + k * qur(1, d, k) - k
  • 第三部分：[dk + 1, len]
    • 所有点都是变到 dk + k 位置后统一变回 1
    • ans = (len - (dk + 1) + 1) * ask(dk + k, k) + (k - 1 + (k - len % k)) * (len - (dk + 1) + 1) / 2

code

int ask(int x, int k) {	// O(log n)
	if(x == 1) return 0;
	if(x % k == 0) return ask(x / k, k) + 1;
	int d = k - x % k;
	return ask((x + d) / k, k) + d + 1;
}
long long qur(long long n, long long k) {
	if(n <= 1) return 0;
	int d = n / k;
	long long ans = (0 + k - 1) * k / 2 * d + d * k + k * qur(d, k) - k;
	long long len = n - d * k;	// 最后一段零散部分长度
	ans += len * ask(d * k + k, k) + (k - 1 + (k - n % k)) * len / 2;
	return ans;
}
void solved() {
	
	int l, r, k;	cin >> l >> r >> k;
	cout << qur(r, k) - qur(l - 1, k) << endl;
	
	return ;
}
signed main() {
	int ttx;  cin >> ttx;  for(int i = 1; i <= ttx; i ++)
		solved();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	int m,j,r,k,s=0;
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>j>>r>>k;
		s=0;
		for(int a=j;a<=r;a++){
			int t=a;
			while(t!=1){
				if(t%k==0){
					t/=k;
					s++;
				}else{
					t++;
					s++;
				}
			}
		}
		cout<<s<<endl;
	}
	
	return 0;
} 

本人市总决赛一样的代码，力竭了，最多20分，参考一下就行了