问题描述
Link to the original problem
这不是一个家庭作业的问题。我只是觉得有人可能知道一个真正的解决这个问题。
It's not a homework question. I just thought that someone might know a real solution to this problem.
我是一个编程大赛早在2004年，而当时这个问题：
I was on a programming contest back in 2004, and there was this problem:
给定n，发现n个数字之和！ n可以是从0到10000的时限：1秒。我认为，有多达100个号码为每个测试组。
我的解决办法是pretty的快，但速度不够快，所以我就让它运行一段时间。它内置，我可以在我的code使用pre计算值的数组。这是一个黑客，但它的工作。
My solution was pretty fast but not fast enough, so I just let it run for some time. It built an array of pre-calculated values which I could use in my code. It was a hack, but it worked.
但是有一个家伙，谁解决了约10行code这个问题，它会给没有时间回答。我相信这是某种形式的动态规划，或从数论东西。我们是16日的时间，所以它不应该是一个火箭科学。
But there was a guy, who solved this problem with about 10 lines of code and it would give an answer in no time. I believe it was some sort of dynamic programming, or something from number theory. We were 16 at that time so it should not be a "rocket science".
有谁知道什么样的算法，他可以使用？
Does anyone know what kind of an algorithm he could use?
修改：我，如果我没有做这个问题清楚遗憾。正如mquander说，应该有一个聪明的解决方案，而不bugnum，只需简单的帕斯卡code，夫妇循环，为O（n ）或类似的东西。大约1秒不是约束了。
EDIT: I'm sorry if I didn't made the question clear. As mquander said, there should be a clever solution, without bugnum, with just plain Pascal code, couple of loops, O(n) or something like that. 1 second is not a constraint anymore.
我发现这里，如果N> 5，那么9分的阶乘的数字之和。我们还可以找到多少个零是有在号码的末尾。我们可以把这个？
I found here that if n > 5, then 9 divides sum of digits of a factorial. We also can find how many zeros are there at the end of the number. Can we use that?
好了，从俄罗斯的编程竞赛的另一个问题。鉴于1＆LT; = N＆LT; = 2 000 000 000，输出N！模（N + 1）。那是某种联系？
Ok, another problem from programming contest from Russia. Given 1 <= N <= 2 000 000 000, output N! mod (N+1). Is that somehow related?
推荐答案
我不知道是谁仍关注此主题，但在这里不用反正。
I'm not sure who is still paying attention to this thread, but here goes anyway.
首先，在官方的前瞻性链接版本，它只有为1000阶乘，不万阶乘。此外，当这个问题在其他程序设计大赛重复使用，期限为3秒，没有1秒。这使得你如何努力必须努力获得足够快的解决方案的巨大差异。
First, in the official-looking linked version, it only has to be 1000 factorial, not 10000 factorial. Also, when this problem was reused in another programming contest, the time limit was 3 seconds, not 1 second. This makes a huge difference in how hard you have to work to get a fast enough solution.
二，比赛的实际参数，彼得的解决方案是合理的，但有一个额外的扭曲，你可以通过5与32位架构的一个因素加速这一过程。 （甚至系数为6，如果只有千！是期望）。即，而不是与个别数字的工作，执行乘法在碱100000然后，在结束时，总的每个超位数内的数字。我不知道你是多么优秀的计算机的较量中允许的，但我有一个台式机在家里是大致一样古老的较量。下面的示例code需要16毫秒，1000！ 2.15秒10000！在code也忽略尾随0，因为他们展现出来，但是这不仅节省约7％的工作。
Second, for the actual parameters of the contest, Peter's solution is sound, but with one extra twist you can speed it up by a factor of 5 with 32-bit architecture. (Or even a factor of 6 if only 1000! is desired.) Namely, instead of working with individual digits, implement multiplication in base 100000. Then at the end, total the digits within each super-digit. I don't know how good a computer you were allowed in the contest, but I have a desktop at home that is roughly as old as the contest. The following sample code takes 16 milliseconds for 1000! and 2.15 seconds for 10000! The code also ignores trailing 0s as they show up, but that only saves about 7% of the work.
#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); }
三，还有一个惊人的，相当简单的方式来加快计算用另外一个大的因素。随着现代方法乘大的数字，它并不需要二次的时间来计算ñ！相反，你可以在O型波浪线（N）时，那里的波浪线意味着您可以在对数因素扔做到这一点。有一个简单的加速由于Karatsuba的不把时间复杂度降低到这一点，但仍提高了它，可以节省4个左右的另一因素。为了使用它，你还需要划分的阶乘本身分成相等大小的范围。你让一个递归算法刺（K，N）倍增的数字，从k以N的伪code公式
Third, there is an amazing and fairly simple way to speed up the computation by another sizable factor. With modern methods for multiplying large numbers, it does not take quadratic time to compute n!. Instead, you can do it in O-tilde(n) time, where the tilde means that you can throw in logarithmic factors. There is a simple acceleration due to Karatsuba that does not bring the time complexity down to that, but still improves it and could save another factor of 4 or so. In order to use it, you also need to divide the factorial itself into equal sized ranges. You make a recursive algorithm prod(k,n) that multiplies the numbers from k to n by the pseudocode formula
prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)
然后你使用Karatsuba的做乘法大导致。
Then you use Karatsuba to do the big multiplication that results.
甚至比Karatsuba的更好的是傅立叶变换为基础的Schonhage-Strassen的乘算法。碰巧的是，这两种算法是现代大数字图书馆的一部分。迅速计算庞大的阶乘可能是某些纯数学应用很重要。我认为Schonhage-Strassen的是矫枉过正的编程比赛。 Karatsuba的是非常简单的，你可以把它想象在A +解决问题的办法。
Even better than Karatsuba is the Fourier-transform-based Schonhage-Strassen multiplication algorithm. As it happens, both algorithms are part of modern big number libraries. Computing huge factorials quickly could be important for certain pure mathematics applications. I think that Schonhage-Strassen is overkill for a programming contest. Karatsuba is really simple and you could imagine it in an A+ solution to the problem.
提出的问题的部分原因是一些猜测，有一个简单的数论把戏，完全改变了比赛的问题。例如，如果问题是确定N！模N + 1，那么威尔逊定理说，答案是-1，当n + 1是素数，这是一个非常简单的锻炼看到它的当n 2 = 3否则为0时，N + 1的组合。有这样太的变动;例如N！也是高度predictable MOD 2N + 1。也有同余和数字总和之间的一些联系。的x模9的数字的总和是也可为x模9，这就是为什么总和为0模9时X = N！对于n> = 6的x模11的位数的交替总和等于x时模11
Part of the question posed is some speculation that there is a simple number theory trick that changes the contest problem entirely. For instance, if the question were to determine n! mod n+1, then Wilson's theorem says that the answer is -1 when n+1 is prime, and it's a really easy exercise to see that it's 2 when n=3 and otherwise 0 when n+1 is composite. There are variations of this too; for instance n! is also highly predictable mod 2n+1. There are also some connections between congruences and sums of digits. The sum of the digits of x mod 9 is also x mod 9, which is why the sum is 0 mod 9 when x = n! for n >= 6. The alternating sum of the digits of x mod 11 equals x mod 11.
现在的问题是，如果你想要的大量数字的总和，而不是什么模，从数论的诡计很快用完了pretty的。添加了的号码的数字不与加法和乘法网眼很好地进行。它往往难以承诺，数学不适合快速算法存在的，但在这种情况下，我不认为有任何已知的公式。例如，我打赌，没有人知道的一个固高阶乘的数字的总和，即使它仅仅是一些数与大约100个数字。
The problem is that if you want the sum of the digits of a large number, not modulo anything, the tricks from number theory run out pretty quickly. Adding up the digits of a number doesn't mesh well with addition and multiplication with carries. It's often difficult to promise that the math does not exist for a fast algorithm, but in this case I don't think that there is any known formula. For instance, I bet that no one knows the sum of the digits of a googol factorial, even though it is just some number with roughly 100 digits.
这篇关于的阶乘的数字总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！