阶乘的数字之和

问题描述 投票：49回答：10

Link to the original problem

这不是一个功课问题。我只是觉得有人可能知道这个问题的真正解决方案。

2004年我参加了编程竞赛，出现了这个问题：

给定n，找到n！的数字之和。 n可以是0到10000.时间限制：1秒。我认为每个测试集最多有100个数字。

我的解决方案非常快，但速度不够快，所以我让它运行一段时间。它构建了一组预先计算的值，我可以在我的代码中使用它。这是一个黑客攻击，但它确实有效。

但有一个人用大约10行代码解决了这个问题，它会立即给出答案。我相信它是某种动态编程，或者来自数论的东西。当时我们16岁，所以它不应该是“火箭科学”。

有谁知道他可以使用什么样的算法？

编辑：如果我没有明确提出问题，我很抱歉。正如mquander所说，应该有一个聪明的解决方案，没有bugnum，只有简单的Pascal代码，几个循环，O（n2）或类似的东西。 1秒不再是约束。

我发现here如果n> 5，则9除以阶乘的数字之和。我们还可以找到数字末尾有多少个零。我们可以用吗？

好的，来自俄罗斯的编程竞赛的另一个问题。给定1 <= N <= 2 000 000 000，输出N！ mod（N + 1）。这有点关系吗？

algorithm dynamic-programming sum-of-digits
10个回答
31
投票

我不确定是谁还在关注这个帖子，但无论如何都要去。

首先，在具有官方外观的链接版本中，它只需要1000个阶乘，而不是10000阶乘。此外，当这个问题在另一个编程比赛中重复使用时，时间限制是3秒，而不是1秒。这对于您需要努力获得足够快的解决方案有很大的不同。

其次，对于比赛的实际参数，彼得的解决方案是合理的，但是通过一个额外的扭曲，您可以使用32位架构将速度提高5倍。 （或者如果只需要1000，则甚至是6倍。）即，不是使用单个数字，而是在基数100000中实现乘法。然后在最后，将每个超数位内的数字相加。我不知道你在比赛中被允许使用的电脑有多好，但我家里有一个桌面，大致和比赛一样古老。 1000以下的示例代码需要16毫秒！万分之一，2.15秒！代码也会在它们出现时忽略尾随0，但这只能节省大约7％的工作量。

#include <stdio.h>
int main() {
    unsigned int dig[10000], first=0, last=0, carry, n, x, sum=0;
    dig[0] = 1;    
    for(n=2; n <= 9999; n++) {
        carry = 0;
        for(x=first; x <= last; x++) {
            carry = dig[x]*n + carry;
            dig[x] = carry%100000;
            if(x == first && !(carry%100000)) first++;
            carry /= 100000; }
        if(carry) dig[++last] = carry; }
    for(x=first; x <= last; x++)
        sum += dig[x]%10 + (dig[x]/10)%10 + (dig[x]/100)%10 + (dig[x]/1000)%10
            + (dig[x]/10000)%10;
    printf("Sum: %d\n",sum); }

第三，有一种令人惊讶且相当简单的方法可以通过另一个相当大的因素来加速计算。使用现代方法来乘以大数，它不需要二次时间来计算n！。相反，你可以在O-tilde（n）时间内完成它，其中波浪线意味着你可以抛出对数因子。有一个简单的加速due to Karatsuba不会带来时间复杂性，但仍然改善它，可以节省另一个因素4左右。为了使用它，您还需要将阶乘本身划分为相等大小的范​​围。你做一个递归算法prod（k，n），用伪代码公式将数字从k乘以n

prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)

然后你使用Karatsuba进行大的乘法运算。

甚至比Karatsuba更好的是基于傅里叶变换的Schonhage-Strassen乘法算法。碰巧，这两种算法都是现代大数字库的一部分。快速计算巨大因子对于某些纯数学应用可能很重要。我认为Schonhage-Strassen对编程竞赛来说太过分了。 Karatsuba非常简单，你可以想象它在问题的A +解决方案中。

提出的部分问题是一些猜测，即有一个简单的数论技巧可以完全改变竞赛问题。例如，如果问题是确定n！ mod n + 1，那么威尔逊定理说当n + 1是素数时答案是-1，并且当n = 3时它看起来是2是非常容易的练习，否则当n + 1是复合时它是0。这也有变化;比如n！也是高度可预测的mod 2n + 1。同余和数字之和之间也存在一些联系。 x mod 9的数字之和也是x mod 9，这就是当x = n时，和为0 mod 9的原因！对于n> = 6. x mod 11的数字的交替和等于x mod 11。

问题在于，如果你想要一个大数字的总和，而不是模数，那么数论的技巧很快就会用完。加上数字的数字与使用进位的加法和乘法不能很好地融合。对于快速算法，通常很难保证数学不存在，但在这种情况下，我认为没有任何已知的公式。例如，我打赌没有人知道googol factorial的数字总和，即使它只是一个大约100位的数字。

0
投票

另一种使用BigInteger的解决方案

 static long q20(){
    long sum = 0;
    String factorial = factorial(new BigInteger("100")).toString();
    for(int i=0;i<factorial.length();i++){
        sum += Long.parseLong(factorial.charAt(i)+"");
    }
    return sum;
}
static BigInteger factorial(BigInteger n){
    BigInteger one = new BigInteger("1");
    if(n.equals(one)) return one;
    return n.multiply(factorial(n.subtract(one)));
}
8
投票

这是A004152中的Online Encyclopedia of Integer Sequences。不幸的是，它没有任何关于如何有效计算它的有用提示 - 它的枫木和mathematica食谱采用了天真的方法。

6
投票

我会攻击第二个问题，计算N！ mod（N + 1），使用Wilson's theorem。这减少了测试N是否为素数的问题。

3
投票

在http://www.penjuinlabs.com/blog/?p=44发现的小而快的python脚本。这是优雅的，但仍然是蛮力。

import sys
for arg in sys.argv[1:]:
    print reduce( lambda x,y: int(x)+int(y), 
          str( reduce( lambda x, y: x*y, range(1,int(arg)))))


$ time python sumoffactorialdigits.py 432 951 5436 606 14 9520
3798
9639
74484
5742
27
141651

real    0m1.252s
user    0m1.108s
sys     0m0.062s
3
投票

假设你有大数字（这是你最小的问题，假设N真的很大，而不是10000），让我们从那里继续。

下面的诀窍是因子N！通过分解所有n <= N，然后计算因子的幂。

有一个计数器矢量;一个计数器，每个素数高达N;将它们设置为0.对于每个n <= N，因子n并相应地增加素数因子的计数器（智能因素：从小素数开始，在分解时构造素数，并记住除以2是移位）。从2的计数器中减去5的计数器，并使计数器为零（这里没有人关心因子10）。

计算所有素数到N，运行以下循环

for (j = 0; j< last_prime; ++j) {
  count[j] = 0;
  for (i = N/ primes[j]; i; i /= primes[j])
    count[j] += i; 
}

请注意，在上一个块中我们只使用（非常）小数字。

对于每个素数因子P，您必须将P计算为适当计数器的幂，使用迭代平方获取对数（计数器）时间;现在你必须乘以素数的所有这些幂。

总而言之，你有关于小数字（log N prime因子）的N log（N）操作，以及对大数字的Log N Log（Log N）操作。

并且在编辑改进之后，对小数字只有N次操作。

HTH

2
投票

1秒？为什么你不能只计算n！并加上数字？这是10000次乘法并且不超过几万次加法，这应该花费大约一万亿分之一秒。

1
投票

你必须计算阶乘。

1 * 2 * 3 * 4 * 5 = 120.

如果您只想计算数字之和，则可以忽略结束零。

6！你可以做12 x 6 = 72而不是120 * 6

7！你可以使用（72 * 7）MOD 10

编辑。

我写得太快了......

10是两个素数2和5的结果。

每次有这两个因素时，您都可以忽略它们。

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15...

1   2   3   2   5   2   7   2   3    2   11    2   13    2    3
            2       3       2   3    5         2         7    5
                            2                  3

因子5出现在5,10,15 ...... 然后在乘以5,10,15之后出现结束零点......

我们有很多2s和3s ......我们很快就会溢出:-(

然后，你仍然需要一个大数字库。

我应该被投票！

0
投票

让我们来看看。我们知道n的计算！对于任何合理大数字，最终会导致一个带有大量尾随零的数字，这些数字对总和没有贡献。沿途砍掉零怎么样？这会使数字的大小更小吗？

嗯。不。我刚刚检查过，整数溢出仍然是一个大问题，即便如此......

0
投票

即使没有任意精度的整数，这也应该是强制性的。在您链接的问题陈述中，需要计算的最大因子是1​​000！。这是一个大约2500位的数字。所以这样做：

  1. 分配一个3000字节的数组，每个字节代表阶乘中的一个数字。以值1开头。
  2. 重复对阵列运行grade-school乘法，以计算阶乘。
  3. 求和数字。

进行重复乘法是唯一可能很慢的步骤，但我确信1000次乘法可以在一秒内完成，这是最坏的情况。如果没有，您可以提前计算一些“里程碑”值，然后将它们粘贴到您的程序中。

一个潜在的优化：当数组出现时消除数组中的尾随零。他们不会影响答案。

显眼注意：我在这里采用编程竞争方法。你可能永远不会在专业工作中这样做。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.