Digit sum【暴力+打表】

Digit sum 33.57% 2000ms 131072K A digit sum S_b(n)S b ​ (n) is a sum of the base-bb digits of nn. Such as S_{10}(233) = 2 + 3 + 3 = 8S 10 ​ (233)=2+3+3=8, S_{2}(8)=1 + 0 + 0 = 1S 2 ​ (8)=1+0+0=1, S_{2}(7)=1 + 1 + 1 = 3S 2 ​ (7)=1+1+1=3.

Given NN and bb, you need to calculate \sum_{n=1}^{N} S_b(n)∑ n=1 N ​ S b ​ (n).

InputFile The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case starts with a line containing two integers NN and bb.

1 \leq T \leq 1000001≤T≤100000

1 \leq N \leq 10^61≤N≤10 6

2 \leq b \leq 102≤b≤10

OutputFile For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 11) and yy is answer.

样例输入 复制 2 10 10 8 2 样例输出 复制 Case #1: 46 Case #2: 13

题目大意： 先输入一个整数$T$，代表有$T$组测试数据，下面$T$行每行输入两个整数$n,b$，先假设函数$f(x,b)$为$x$转换为$b$进制后各数位的和，例如$f(8,2)=1,f(10,10)=1$，求${\sum }_{i=1}^{n}f(i,b)$

解题思路： 此题无需想的太复杂，因为$1\le n\le 1e6$，且$2\le b\le 10$，所以可以将$1e6$以内所有的情况全都暴力打出来，最后$O(1)$输出即可。

代码:

//#pragma GCC optimize(3,"Ofast","inline") #include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; int get_sum(int n,int b) { int sum=0; while(n) { sum+=n%b; n=n/b; } return sum; } int sum[1000100][11]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif //ios::sync_with_stdio(0),cin.tie(0); rep(i,1,1000000) { rep(j,2,10) { sum[i][j]=sum[i-1][j]+get_sum(i,j); } } int T; scanf("%d",&T); rep(t,1,T) { int n,b; scanf("%d %d",&n,&b); printf("Case #%d: %d\n",t,sum[n][b]); } return 0; }