D i g i t <mtext>   </mtext> s u m Digit\ sum Digit sum

题目描述见链接 .

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

按位处理, 设当前进制为 B B B, 计算第 b i t bit bit 位的答案,
有 这道题 作基础, 可以知道形如 0 , 0 , . . 1 , 1.. , 2 , 2 , . . B − 1 , B − 1 0,0,..1,1..,2,2,..B-1,B-1 0,0,..1,1..,2,2,..B−1,B−1 的循环节长度为 c i r _ l e n = B b i t + 1 cir\_len=B^{bit+1} cir_len=Bbit+1,
循环节内部最长连续数字为 B b i t B^{bit} Bbit 个,
完整的循环节个数为 c i r _ n u m = N + 1 B b i t + 1 cir\_num=\frac{N+1}{B^{bit+1}} cir_num=Bbit+1N+1​, 对答案贡献为 B ( B − 1 ) 2 ∗ B b i t ∗ c i r _ n u m \frac{B(B-1)}{2}*B^{bit}*cir\_num 2B(B−1)​∗Bbit∗cir_num .

还剩余一个不完整的循环节, 长度为 s c a _ n u m = ( N + 1 ) % B b i t + 1 sca\_num = (N+1)\%B^{bit+1} sca_num=(N+1)%Bbit+1, 在这个循环节中, 将形如 1 , 1 , . . 1 1,1,..1 1,1,..1 看成新的循环节,
得到新的 c i r _ l e n = B b i t cir\_len = B^{bit} cir_len=Bbit, c i r _ n u m = s c a _ n u m B b i t cir\_num=\frac{sca\_num}{B^{bit}} cir_num=Bbitsca_num​, 对答案贡献为 c i r _ n u m ( c i r _ n u m − 1 ) 2 ∗ c i r _ l e n \frac{cir\_num(cir\_num-1)}{2}*cir\_len 2cir_num(cir_num−1)​∗cir_len,

然而还是会剩下不完整的形如 2 , 2 2, 2 2,2 这样的小循环节, 长度为 l e f t _ n u m = s c a _ n u m % c i r _ l e n left\_num = sca\_num \% cir\_len left_num=sca_num%cir_len,
对 答案贡献 为 l e f t _ n u m ∗ c i r _ n u m left\_num * cir\_num left_num∗cir_num .

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

#include<bits/stdc++.h>
#define reg register

int N;
int B;
int Ans;
int Case_cnt;
int pw[20][21];

void Work(){
        scanf("%d%d", &N, &B);
        Ans = 0;
        for(reg int bit = 0; pw[B][bit] <= N+1; bit ++){
                int cir_len = pw[B][bit+1];
                int cir_num = (N+1) / cir_len; 
                Ans += pw[B][bit] * cir_num * B*(B-1)/2;
                int sca_num = (N+1) % cir_len;
                if(!sca_num) continue ;
                cir_len = pw[B][bit];
                cir_num = sca_num / cir_len;
                Ans += cir_len * cir_num*(cir_num-1)/2;
                int left_num = sca_num % cir_len;
                Ans += left_num * cir_num;
        }
        printf("Case #%d: %d\n", ++Case_cnt, Ans);
}

void Init(){
        for(reg int i = 2; i <= 11; i ++){
                pw[i][0] = 1;
                for(reg int j = 1; j <= 20; j ++) pw[i][j] = pw[i][j-1] * i;
        }
}
int main(){
        int T;
        scanf("%d", &T);
        Init();
        while(T --) Work();
        return 0;
}