#include iostream#include cmathusing namespace std;typedef long long LL;LL l r k;int q;LL calcLL x LL res = 0; for LL i = 1; i = x; i = k res += x i; return res;int main cin q; whil

优化思路：

1. 对于每个询问，可以先预处理出区间 $[1,r]$ 内每个数的 $k$ 进制下的数位和，记为 $s_i$，可以用类似于计算阶乘的方法进行预处理：从 $1$ 枚举到 $r$，每次枚举时对于当前数 $i$，计算出 $i$ 在 $k$ 进制下的各个数位上的值，然后累加起来即可。
2. 对于每个询问，可以先用二分查找找到区间 $[1,r]$ 内第一个数 $x$ 满足 $s_x\geq l$，然后再用二分查找找到区间 $[1,r]$ 内第一个数 $y$ 满足 $s_y>r$，那么符合条件的数就是 $[x,y-1]$，个数为 $y-x$。 具体实现可以参考下面的代码：