[RC-07] 心跳题解

Demeanor_Roy · 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，接下来分两种情况计算答案：

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

[RC-07] 心跳 题解

[RC-07] 心跳题解