我不确定谁还在关注这个线程，但无论如何都会这样。
首先，在官方外观的链接版本中，它只需 1000 阶乘，而不是 10000 阶乘。另外，当这个问题在另一个编程比赛中被重用时，时间限制是 3 秒，而不是 1 秒。这对您获得足够快的解决方案所付出的努力有很大的影响。
其次，对于比赛的实际参数，Peter 的解决方案是合理的，但如果使用 32 位架构，您可以将其速度提高 5 倍。（如果只需要 1000，甚至是 6 倍！）也就是说，不是使用单个数字，而是在基数 100000 中实现乘法。最后，将每个超数字内的数字相加。我不知道你在比赛中被允许使用的电脑有多好，但我家里有一台与比赛一样古老的台式机。下面的示例代码 1000 需要 16 毫秒！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-波浪号 (n) 时间内执行此操作，其中波浪号表示您可以加入对数因子。由于 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 阶乘的位数之和，即使它只是一个大约 100 位数的数字。