阶乘的数字之和
链接到原来的问题
这不是一个功课问题。 我只是以为有人可能知道这个问题的真正的解决scheme。
2004年我参加了一个编程比赛，出现了这个问题：
给定n，findn！的数字的总和。 n可以从0到10000.时间限制：1秒。 我认为每个testing集有多达100个数字。
我的解决scheme非常快但速度不够快，所以我只是让它运行一段时间。 它build立了一个预先计算的值的数组，我可以在我的代码中使用。 这是一个黑客，但它的工作。
但是有一个人用十行代码解决了这个问题，很快就会给出答案。 我相信这是某种dynamic规划，或者是数理论。 当时我们是16岁，所以不应该成为“火箭科学”。
有谁知道他可以使用什么样的algorithm？
编辑 ：对不起，如果我没有明确的问题。 正如mquander所说，应该有一个聪明的解决scheme，没有bugnum，只有普通的Pascal代码，几个循环，O（n 2 ）或类似的东西。 1秒不再是一个约束。
我在这里发现，如果n> 5，那么9除以阶乘的数字之和。 我们还可以find数字末尾有多less个零。 我们可以使用它吗？
好吧，来自俄罗斯的编程比赛的另一个问题。 给定1 <= N <= 2000000000，输出N！ mod（N + 1）。 这有什么关系？
我不确定谁仍然关注这个线程，但是无论如何，
首先，在官方的链接版本中，它只需要1000个因子，而不是10000个因子。 而且，当这个问题在另一个编程比赛中被重用时，时间限制是3秒，而不是1秒。 这对于获得足够快的解决scheme需要多大的努力才能产生巨大的影响。
其次，对于比赛的实际参数，彼得的解决scheme是完善的，但有一个额外的扭曲，你可以使用32位架构加速5倍。 （如果只需要1000个，甚至是6的倍数）。也就是说，不用个别数字来处理，而是以100000为基数进行乘法运算。最后，在每个超数字内累加数字。 我不知道在比赛中你有多么好的电脑，但是我有一个和比赛大致相同的台式机。 下面的示例代码需要16毫秒1000！ 10000秒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）的时间内做到这一点，其中代字号意味着你可以抛出对数因子。 由于Karatsuba有一个简单的加速，并没有把时间复杂度降低到这个水平，但是仍然提高了它，并且可以保存另外四个因子。 为了使用它，还需要将因子本身分成相等大小的范围。 你做了一个recursionalgorithmprod（k，n），把k到n的数字乘以伪代码公式
prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)
然后你使用Karatsuba来做大的乘法运算。
甚至比Karatsuba更好的是基于傅立叶变换的Schonhage-Strassen乘法algorithm。 碰巧，这两种algorithm都是现代大数字图书馆的一部分。 快速计算巨大的因式分解可能对于某些纯粹的math应用很重要。 我认为Schonhage-Strassen是一个编程比赛的矫枉过正。 Karatsuba非常简单，您可以在A +解决scheme中想像这个问题。
问题的一部分是一些猜测，有一个简单的数字理论技巧，完全改变比赛的问题。 例如，如果问题是确定n！ 那么威尔逊定理说，当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。
问题是，如果你想要一个大数字的总和，而不是任何模数，数论的技巧运行得非常快。 加上一个数字的数字不能很好地与进位相加和相乘。 通常很难保证algorithm不存在，但在这种情况下，我不认为有任何已知的公式。 例如，我敢打赌，没有人知道一个googol因子的数字的总和，即使它只是一些大约100位数的数字。
这是整数序列在线百科全书中的 A004152 。 不幸的是，它没有任何关于如何有效地计算它的有用的提示 – 它的枫树和mathematica食谱采取天真的方法。
我会攻击第二个问题，计算N！ mod（N + 1），使用威尔逊定理 。 这就减less了testingN是否为素数的问题。
在http://www.penjuinlabs.com/blog/?p=44上find一个小而快的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
假设你有大数字（这是你的问题中最less的，假设N很大，而不是10000），让我们继续。
下面的诀窍是要素N！ 通过分解所有n <= N，然后计算因子的幂。
有一个柜台的vector; 每个质数最多N个计数器; 将它们设置为0.对于每个n <= N，因子n，并相应地增加素因子的计数器（巧妙地因素：以小素数开始，在因式分解的基础上构build素数，记住2除以移位）。 从2的计数器减去5的计数器，并使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素数因子）和日志N日志（日志N）操作进行N日志（N）操作。
编辑
而在编辑完成之后，只有N个小号码的操作。
编辑结束
HTH
1秒？ 为什么你不能计算n！ 并加起来的数字？ 这是10000次乘法，不超过几万次，这大约需要十亿分之一秒。
让我们来看看。 我们知道n的计算！ 对于任何相当多的数字，最终都会导致一个有很多尾随零的数字，而这些数字并不会影响总和。 如何一路砍掉零点？ 这会保持数字的小一点？
嗯。 不。 我刚刚检查，整数溢出仍然是一个大问题，即使…
你必须计算fatcorial。
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 …我们很快就会溢出:-(
那么，你仍然需要一个大数据库。
我值得被低估！
即使没有任意的精度整数，这应该是暴躁的。 在你连接的问题陈述中，需要计算的最大因子是1000！ 这是一个大约2500位数的数字。 所以就这样做：
- 分配一个3000字节的数组，每个字节代表阶乘中的一个数字。 从1开始。
- 重复在数组上执行小学乘法，以计算阶乘。
- 总和数字。
重复乘法是唯一可能的缓慢步骤，但是我确信1000次乘法可以在一秒钟内完成，这是最糟糕的情况。 如果不是的话，你可以提前计算一些“里程碑”的值，并把它们粘贴到你的程序中。
一个潜在的优化：当数组出现时消除数组中的尾随零。 他们不会影响答案。
显而易见的是：我正在采取一种编程竞争的方式。 你可能永远不会做专业的工作。
另一个使用BigInteger的解决scheme
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))); }
