阶乘的数字之和

Question

链接到原始问题

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

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

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

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

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

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

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

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

好的,来自俄罗斯的编程竞赛的另一个问题.给定1 <= N <= 2 000 000 000,输出N!mod(N + 1).这有点关系吗？

Answer 1

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

首先,在具有官方外观的链接版本中,它只需要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)时间内完成它,其中波浪线意味着你可以抛出对数因子.由于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位的数字.

Answer 2

这是A004152在整数序列的在线百科全书.不幸的是,它没有任何关于如何有效计算它的有用提示 - 它的枫树和数学方法采用了天真的方法.

Answer 3

我会攻击第二个问题,计算N!mod(N + 1),使用Wilson定理.这减少了测试N是否为素数的问题.

Answer 4

1秒？为什么你不能直接计算 n! 并将数字相加？这相当于 10000 次乘法和不超过几万次加法，大约需要十亿分之一秒。