求1到n的数位和，要求O(n)的复杂度

lsmCC

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int f(int n)
   
5. {
   
6.     string str = to_string(n);
   
7.     int sum_1 = 0;
   
8.     for (char ch : str) {
   
9.         sum_1 += ch - '0';
   
10.     }
    
11.     return sum_1;
    
12. }
    
13. 
    
14. void solve()
    
15. {
    
16.     long long n;
    
17.     cin >> n;
    
18.     long long sum = 0;
    
19.     for (int i = 1; i <= n; i++) {
    
20.         sum += f(i);
    
21.     }
    
22.     cout << sum << endl;
    
23. }参考代码如下
    
24. 
    
25. int main()
    
26. {
    
27.     int t;
    
28.     cin >> t;
    
29.     while (t--) {
    
30.         solve();
    
31.     }
    
32.     return 0;
    
33. }

复制代码

FishC

题目要求计算从1到n的数位和，要求复杂度为O(n)。下面是一个符合要求的解法。

首先，我们可以观察到从1到n的每个数字的数位和都是从1到n最高位的数位和的累加。例如，从1到100的数位和等于从1到99的数位和加上100的数位和。因此，我们可以使用动态规划来解决这个问题。

具体的步骤如下：

1. 创建一个长度为n+1的数组sums，用来存储从1到n的每个数字的数位和。
2. 初始化sums[0]为0。
3. 从1到n，遍历每个数字i：
   a. 获取数字i的最低位digit：digit = i % 10。
   b. 更新数字i的数位和为sums = sums[i / 10] + digit。
4. 返回sums[n]作为结果。

下面是对应的C++代码：

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. int getDigitSum(int n) {
   
6.     vector<int> sums(n+1, 0);
   
7.     for (int i = 1; i <= n; i++) {
   
8.         int digit = i % 10;
   
9.         sums[i] = sums[i / 10] + digit;
   
10.     }
    
11.     return sums[n];
    
12. }
    
13. 
    
14. int main() {
    
15.     int n;
    
16.     cout << "请输入一个整数n：";
    
17.     cin >> n;
    
18.     int result = getDigitSum(n);
    
19.     cout << "从1到" << n << "的数位和为：" << result << endl;
    
20.     return 0;
    
21. }

复制代码

这段代码中，我们首先定义了一个名为getDigitSum的函数，用来计算从1到n的数位和。在主函数中，我们输入一个整数n，并调用getDigitSum函数来计算结果，然后输出结果。

希望对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

zhangchenyvn

1:将数字转换成str
2:数一下位数（strlen）
3:输出45*1+45*11+45*111+…+45*111（strlen个1）111
4:试一下！！

zhangjinxuan

严格来说不会有 $O(n)$ 的时间复杂度，这个代码还是 $O(n \log_{10} n)$ 的复杂度。

不过你可以使用数位DP将时间复杂度做到 $O(\log_{10} n)$，虽然并不是楼主需要的 $O(n)$，但是这个算法比 $O(n)$ 算法优秀得多，可以解决 $n=10^{18}$ 甚至更大的情况。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. #define int long long
   
4. int d[18], m;
   
5. long long l, r;
   
6. 
   
7. struct Info {
   
8.         int a[10], numtot;
   
9.         const Info operator + (const Info &i) const {
   
10.                 Info res = {{}, numtot + i.numtot};
    
11.                 for (int j = 0; j <= 9; ++j) res.a[j] = a[j] + i.a[j];
    
12.                 return res;
    
13.         }
    
14.         const Info operator - (const Info &i) const {
    
15.                 Info res = {{}, numtot - i.numtot};
    
16.                 for (int j = 0; j <= 9; ++j) res.a[j] = a[j] - i.a[j];
    
17.                 return res;
    
18.         }
    
19. } f[21][2][2];
    
20. 
    
21. Info calc(int i, int zero, int limited) {
    
22.         if (i == m + 1) return {{}, zero};
    
23.         if (f[i][zero][limited].numtot != -1) return f[i][zero][limited];
    
24.         Info res = {{}, 0};
    
25.         if (i == 1) {
    
26.                 for (int j = 0; j <= d[1]; ++j) {
    
27.                         Info tmp = calc(i + 1, (j != 0), (j != d[1]));
    
28.                         res = res + tmp;
    
29.                         if (j != 0) {
    
30.                                 res.a[j] += tmp.numtot;
    
31.                         }
    
32.                 }
    
33.         } else {
    
34.                 if (limited) {
    
35.                         for (int j = 0; j <= 9; ++j) {
    
36.                                 Info tmp = calc(i + 1, (bool)(zero | j), 1);
    
37.                                         res = res + tmp;
    
38.                                 if ((bool)(zero | j)) {
    
39.                                 res.a[j] += tmp.numtot;
    
40.                                 }
    
41.                         }
    
42.                 } else { // ???üì? 0 ~ d[i] μ?????￡?2￠?ú×?òa?ó
    
43.                         for (int j = 0; j <= d[i]; ++j) {
    
44.                                 Info tmp = calc(i + 1, (bool)(zero | j), (j != d[i]));
    
45.                                         res = res + tmp;
    
46.                                 if ((bool)(zero | j)) {
    
47.                                 res.a[j] += tmp.numtot;
    
48.                                 }
    
49.                         }
    
50.                 }
    
51.         }
    
52.         return f[i][zero][limited] = res;
    
53. }
    
54. 
    
55. signed main() {
    
56.     int t = 1;
    
57.         while (t--) {
    
58.             l = 1;
    
59.             scanf("%lld", &l, &r);
    
60.                 m = 0;
    
61.                 for (long long tr = r; tr; tr /= 10)
    
62.                         d[++m] = tr % 10;
    
63.                 for (int i = 1, j = m; i < j; ++i, --j) swap(d[i], d[j]);
    
64.                 for (int i = 0; i < 21; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) f[i][j][k].numtot = -1;
    
65.                 Info tmp = calc(1, 0, 0);
    
66.                 if (l != 1) {
    
67.                         m = 0;
    
68.                         memset(d, 255, sizeof(d));
    
69.                         for (long long tr = l - 1; tr; tr /= 10)
    
70.                                 d[++m] = tr % 10;
    
71.                         for (int i = 1, j = m; i < j; ++i, --j) swap(d[i], d[j]);
    
72.                 for (int i = 0; i < 21; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) f[i][j][k].numtot = -1;
    
73.                         tmp = tmp - calc(1, 0, 0);
    
74.                 }
    
75.                 long long res = 0;
    
76.                 for (int i = 1; i <= 9; ++i) res += tmp.a[i] * i;
    
77.                 printf("%lld\n", res);
    
78.         }
    
79. //        printf("%lld\n", tmp.numtot);
    
80.         return 0;
    
81. }
    
82. /*
    
83. 01
    
84. */

复制代码