查找十进制数字总和的最快方法

Question

找到十进制数字总和的最快方法是什么？以下代码是我写的,但是范围非常慢1 to 1000000000000000000

long long sum_of_digits(long long input) {
    long long total = 0;
    while (input != 0) {
        total += input % 10;
        input /= 10;
    }
    return total;
}

int main ( int argc, char** argv) {
    for ( long long i = 1L; i <= 1000000000000000000L; i++) {
        sum_of_digits(i);
    }
    return 0;
}

Answer 1

我假设你要做的是沿着这条线

#include <iostream>
const long long limit = 1000000000000000000LL;
int main () {
   long long grand_total = 0;
   for (long long ii = 1; ii <= limit; ++ii) {
      grand_total += sum_of_digits(i);
   }
   std::cout << "Grand total = " << grand_total << "\n";
   return 0;
}

这不会有两个原因:

• 这需要很长时间.
• 它会溢出.

要处理溢出问题,您将需要设置上限或使用一些bignum包.我会把解决这个问题留给你.

为了应对您需要创造性的计算负担.如果你知道上限限制为10的幂,这相当容易.如果上限可以是任意数字,则必须更具创造性.

首先看一下计算从0到10 ⁿ -1 的所有整数的位数之和的问题(例如,0到9(n = 1),0到99(n = 2)等)表示数字之和从10 ⁿ -1到S _n的所有整数.对于n = 1(0到9),这仅是0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45(9*10/2).因此S ₁ = 45.

对于n = 2(0到99),你总计0-9十次,你再次总结0-9十次.对于n = 3(0到999),您将总计0-99十次,并且您将0-9 100次相加.对于n = 4(0到9999),您将总计0-999十次,并且您将0-9 1000次相加.通常,S _n = 10S _n-1 + 10 ^n-1 S ₁作为递归表达式.这简化为S _n =(9n10 ⁿ)/ 2.

如果上限为形式10的^Ñ,解决方案是以上步骤S _Ñ加一更为号1000 ... 000.如果上限是任意数字,您将需要再次创作.想一想为S _n制定公式的方法.