# 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; } ```