# The Preliminary Contest for ICPC Asia Shanghai 2019  ***** **数字求和** 一个数字和S (n)是n的b进制数字的和，如S10(233)=2+3+3=8,S2(8)= 1+0+0= 1,S2(7)=1+1+1=3。 给定N和b，你需要计算Sb(n)~ (N)的值。 **输入** 输入的第一行给出了测试用例的数量，接下来是T 测试用例。每个测试用例都以包含两个整数N和b的行开始。 **输出** 对于每个测试用例，输出一行包含*Case#x: y*，其中x是测试用例号(从1开始)，y是答案。 :-: **求得每个数对应b进制时，各个位数上的数字相加之和。** ``` int calc(int n,int b) { int res=0; while(n) { res += (n%b); n/=b; } return res; } ``` ***** ``` for(int i=1;i<=N;i++) { sum = cal(b,i); } ``` #### [树状数组](https://baike.so.com/doc/7865826-8139921.html)的扩展。 > 树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和， >   ***** :-: **有该函数才有y的二进制数的lowbit()操作的实现。** ``` int lowbit(int x) { return x&(-x); } ``` ***** ``` void add(int x,int y,int val) { while(y<MAXN) { c[x][y]+=val; y+=lowbit(y);//y的二进制数+1的操作 } } int Sum(int x,int y) { int sum = 0; while(y>0) { sum+=c[x][y]; y-=lowbit(y);//y的二进制数-1的操作 } return sum; }//将c[x][y]进行一次相加，直到所有数值相加完成 ``` ***** ``` const int MAXN = 1000001; int c[11][MAXN]; ``` ***** ``` #include<iostream> using namespace std; const int MAXN = 1000001; int c[11][MAXN]; int calc(int n,int b) { int res=0; while(n) { res += (n%b); n/=b; } return res; }//求得每个数对应b进制时，各个位数上的数字相加之和。 int lowbit(int x) { return x&(-x); }//有该函数才有y的二进制数的lowbit()操作的实现。 void add(int x,int y,int val) { while(y<MAXN) { c[x][y]+=val; y+=lowbit(y);//y的二进制数+1的操作 } } int Sum(int x,int y) { int sum = 0; while(y>0) { sum+=c[x][y]; y-=lowbit(y);//y的二进制数-1的操作 } return sum; }//将c[x][y]进行一次相加，直到所有数值相加完成 void init() {//将二到十进制的所有数的情况计算出来，且对每个进制建立一个树状数组 for(int i=2;i<=10;i++) { for(int j=1;j<MAXN;j++) { int val = calc(j,i);//将cal函数求得的和赋予val add(i,j,val);//对应1到n的数，各位的val值赋予未定义的c[b][n] } } } int main() { int T,id=1; init(); scanf("%d",&T); while(T--) { int n,b; scanf("%d%d",&n,&b); printf("Case #%d: %d\n",id++,Sum(b,n)); } return 0; } ```