题目链接
Digit sum
思路
这题就是计算1-n的各个位数之和，那么我们可以对每个位置进行统计。
例如，328，
先看百位
3(28+1)
2100
1100
再看十位
2(8+1)
110
这时候需要计算111 112 中的十位
也就是1+2+3+4+5+6+7+8+9=45,计算有多少个45.注意，这时候先不看个位。我们有110 120 130 140 150 160 ~290 ，也就是有3组，就是34510.
然后再看个位8+7+6+5+4+3+2+1，然后4532*1；
就好了
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
long long sumOfDigits(int n,int b) {
int sums[11];
int m=n;
long long sum = 0;
for(int i = 0; i <= b; i++) {
sum += i;
sums[i+1] = sum;
}
sum=0;
vector<int>nums;
queue<int>num;
while(n)
{
nums.push_back(n%b);
n/=b;
}
for(int i=nums.size()-1;i>=0;i--)
{
num.push(nums[i]);
}
int now = 0;
while(!num.empty())
{
int x=num.front();num.pop();
int len = num.size();
sum+=x*(m-pow(b,len)*x+1);
m-=pow(b,len)*x;
sum+=sums[x]*pow(b,len);
sum+=sums[b]*now*pow(b,len);
now*=b;
now+=x;
}
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,x;
scanf("%d %d",&n,&x);
printf("%lld\n",sumOfDigits(n,x));
}
}
|