自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:44:29，当前版本为作者最后更新于2023-02-03 16:06:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 个人感觉略显套路。

考虑怎样一个数才能称作 $B$-好的，这里给出结论：

• 当且仅当数 $x$ 在 $B$ 进制下，去除最高位最多有一位为 $B-2$，其余均为 $B-1$ 时，我们称数 $x$ 是 $B$-好的。

证明的话考虑对每个数 $x$，构造一个小于 $x$ 且 $B$ 进制下数位和最大的数，不难发现将最高位减一，其余位全取 $B-1$ 即可得到，所以如果 $x$ 是 $B$-好的，其在 $B$ 进制下数位和必须大于等于这个数的数位和。于是简单讨论可得以上结论。

对于数 $x$，令其 $B$ 进制下位数为 $len$，最高位为 $m$，接下来分两种情况计算答案：

1. 最高位未满，显然可以直接列出式子：$ans = \frac{len(len-1)(B-1)}{2} + (m-1)len$。其中前者是位数小于 $len$ 的答案求和，后者是最高位为 $[1,m-1]$ 的答案求和。不懂的可以看 这儿。

2. 最高位已满，这样的答案只有 $\log$ 个，暴力比较是否合法即可。

时间复杂度 $O(T \log n)$。下附代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int N=65;
int T;
LL n,B,now,ans,num[N];
inline void solve()
{
	scanf("%lld%lld",&n,&B);
	now=0;
	while(n) num[++now]=n%B,n/=B;
	ans=(B-1)*now*(now-1)/2+(num[now]-1)*now;
	for(int i=now-1;i>=1;i--)
	{
		if(num[i]==B-1) ans+=(i==1)+1;
		else if(num[i]==B-2)
		{
			bool flag=true;
			for(int j=i-1;j>=1;j--)	if(num[j]!=B-1) {flag=false;break;}
			if(flag) ans++;break;
		}
		else break;
	}
	printf("%lld\n",ans+(now==1));
}
int main()
{
	scanf("%d",&T);
	while(T--)	solve();
	return 0;
}