[The Preliminary Contest for ICPC Asia Nanjing 2019] L-Digit sum

题意

---

$S_{b}(n)$表示数字$n$在$b$进制下各位的和，对于给定的数$N$和$b$，求出$sum_{n=1}^{N}S_{b}(n)$ $[ link ]$

分析

---

题解上写的是签到题，这是个悲伤的故事。

直接$b$进制分解求$S_{b}(n)$，先预处理出$a[i][j]$表示$i$进制下从$1$到$j$每个数各位数求和后的总和

对于每组数据$O(1)$输出即可

Code

#include <cstdio>
const int n = 1e6+5;
int a[11][n];
int t, N, b;
int main()
{
    scanf("%d", &t);
    for (int i = 2; i <= 10; i++) {
        for (int j = 1; j < n; j++) {
            int sum = 0, p = j;
            while(p>0) {
                sum += p%i;
                p /= i;
            }
            a[i][j] = a[i][j-1] + sum;
        }
    }
    
    for (int i = 1; i <= t; i++) {
        scanf("%d%d", &N, &b);
        printf("Case #%d: %d
", i, a[b][N]);
    }
}