1

如果我有点傻，请原谅我，但我最近才开始编程，在 Project Euler 上做问题 160 可能有点超出我的深度。我已经尝试解决它，但似乎在任何个人计算机上处​​理 1tn 数字都需要很长时间，所以我想我应该研究数学以找到一些捷径。

欧拉计划问题 160：

对于任何 N，令 f(N) 为 N! 中尾随零之前的最后五位数字。例如，

9！= 362880 所以 f(9)=36288 10！= 3628800 所以 f(10)=36288 20！= 2432902008176640000 所以 f(20)=17664

求 f(1,000,000,000,000)

新尝试：

#include <stdio.h>


main()
{
    //I have used long long ints everywhere to avoid possible multiplication errors
    long long f; //f is f(1,000,000,000,000)
    f = 1;
    for (long long i = 1; i <= 1000000000000; i = ++i){
        long long p;
        for (p = i; (p % 10) == 0; p = p / 10) //p is i without proceeding zeros
            ;
        p = (p % 1000000); //p is last six nontrivial digits of i
        for (f = f * p; (f % 10) == 0; f = f / 10)
            ;
        f = (f % 1000000); 
    }
    f = (f % 100000);
    printf("f(1,000,000,000,000) = %d\n", f);
}

旧尝试：

#include <stdio.h>

main()
{
    //This part of the programme removes the zeros in factorials by dividing by 10 for each factor of 5, and finds f(1,000,000,000,000) inductively
    long long int f, m; //f is f(n), m is 10^k for each multiple of 5
    short k; //Stores multiplicity of 5 for each multiple of 5
    f = 1;
    for (long long i = 1; i <= 100000000000; ++i){
        if ((i % 5) == 0){
            k = 1;
            for ((m = i / 5); (m % 5) == 0; m = m / 5) //Computes multiplicity of 5 in factorisation of i
                ++k;
            m = 1;
            for (short j = 1; j <= k; ++j) //Computes 10^k
                m = 10 * m;
            f = (((f * i) / m) % 100000);
        }
        else f = ((f * i) % 100000);
    }
    printf("f(1,000,000,000,000) = %d\n", f);
}
4

5 回答 5

1

问题是：

对于任何N，让f(N)成为 中尾随零之前的最后五位数字N!。寻找f(1,000,000,000,000)

让我们重新表述这个问题：

对于任何N，让g(N)成为 中尾随零之前的最后五位数字N。对于任何N，让。找到。f(N)g(N!)f(1,000,000,000,000)

现在，在你编写代码之前，用数学方法证明这个断言：

  • 对于任何N > 1,f(N)等于g(f(N-1) * g(N))

请注意，我自己并没有证明这一点；我可能在这里犯了一个错误。（更新：这似乎是错误的！我们将不得不对此多加考虑。）证明它让您满意。您可能希望从证明一些中间结果开始，例如：

  • g(x * y) = g(g(x) * g(y))

等等。

一旦你获得了这个结果的证明，现在你就有了一个递归关系，你可以用它来找到任何f(N)，并且你必须处理的数字永远不会比 大得多N。

于 2014-05-15T22:57:56.343 回答
1 
Prod(n->k)(k*a+c) mod a <=> c^k mod a

例如

prod[ 3, 1000003, 2000003,... , 999999000003 ] mod 1000000

等于

3^(1,000,000,000,000/1,000,000) mod 1000000

和 N 中尾随 0 的数量！等于 N 的因式分解中的 5！

于 2014-05-17T08:10:42.220 回答
0

我会计算整个事情，然后将第一个非零数字与 LSB 分开......但对你来说，我认为这更好：

1.使用更大的底座

  • 任何数都可以重写为相同数（基数）的幂次之和

  • 像 1234560004587786542 可以重写为基础b=1000 000 000，如下所示：

    1*b^2 + 234560004*b^1 + 587786542*b^0

2.当你相乘时，低位仅取决于相乘数字的最低位

A*B = (a0*b^0+a1*b^1+...)*(b0*b^0+b1*b^1+...)
     = (a0*b0*b^0)+ (...*b^1) + (...*b^2)+ ...

3.放在一起

for (f=1,i=1;i<=N;i++)
 {
 j=i%base;
 // here remove ending zeroes from j
 f*=j;
 // here remove ending zeroes from f
 f%=base;
 }
  • 不要忘记变量 f 必须足够大以容纳 base^2
  • 并且 base 必须至少比 100000 大 2 位才能覆盖 5 位并溢出到零
  • 基数必须是 10 的幂才能保留十进制数字

[edit1] 实现

uint<2> f,i,j,n,base;   // mine 64bit unsigned ints (i use 32bit compiler/app)
base="10000000000";     // base >= 100000^2 ... must be as string to avoid 32bit trunc
n="20";                 // f(n) ... must be as string to avoid 32bit trunc
for (f=1,i=1;i<=n;i++)
    {
    j=i%base;
    for (;(j)&&((j%10).iszero());j/=10);
    f*=j;
    for (;(f)&&((f%10).iszero());f/=10);
    f%=base;
    }
f%=100000;
int s=f.a[1];           // export low 32bit part of 64bit uint (s is the result)

太慢了:(

f(1000000)=12544 [17769.414 ms]
f(     20)=17664 [     0.122 ms]
f(     10)=36288 [     0.045 ms]

为了更快的速度或使用任何快速的阶乘实现

[edit2] 只是多了几个 32 位 n！测试的阶乘

此声明无效:(

//You could attempt to exploit that 
//f(n) = ( f(n%base) * (f(base)^floor(n/base)) )%base
//do not forget that this is true only if base fulfill the conditions above

幸运的是，这似乎是真的:) 但前提是（a 比 b 大得多并且 a%base=0）

g((a+b)!)=g(g(a!)*g(b!))
// g mod base without last zeroes...
// this can speed up things a lot

f(                1)=00001
f(               10)=36288
f(              100)=16864
f(            1,000)=53472
f(           10,000)=79008
f(          100,000)=56096
f(        1,000,000)=12544
f(       10,000,000)=28125

f(        1,000,100)=42016
f(        1,000,100)=g(??????12544*??????16864)=g(??????42016)->42016
  • 越接近 b 的有效数字越少！！！
  • 这就是为什么 f(1001000) 不起作用...
于 2014-05-16T17:00:20.683 回答
0

我不是专家项目欧拉求解器，而是对所有欧拉问题的一些一般性建议。

1 - 首先以最明显的方式解决问题。这可能会为以后的尝试带来见解

2 - 在更小的范围内解决问题。Euler 通常会给出可用于检查算法的较小范围的答案

3 - 扩大问题规模并计算问题将如何扩大规模，时间方面，随着问题变得更大

4 - 如果解决方案需要的时间超过几分钟，那么是时候检查算法并提出更好的方法了

5 - 记住欧拉问题总是有答案的，并且依赖于聪明的编程和聪明的数学的结合

6 - 一个被很多人解决的问题不可能是错的，是你错了！

我最近使用这些步骤解决了 phidigital 数字问题（Euler 的网站已关闭，无法查找该数字，在发布时它是最近的）。我最初的蛮力算法需要 60 小时，我查看了解决 1,000,000 个显示的模式，并获得了找到需要 1.25 秒的解决方案的洞察力。

于 2014-06-18T01:35:10.283 回答
0

分别处理以 2、4、5、6、8、0 结尾的数字可能是一个想法。以 1、3、7、9 结尾的数字不能产生尾随零。让

A(n) = 1 * 3 * 7 * 9 * 11 * 13 * 17 * 19 * ... * (n-1).
B(n) = 2 * 4 * 5 * 6 * 8 * 10 * 12 * 14 * 15 * 16 * 18 * 20 * ... * n.

n 的阶乘是 A(n)*B(n)。我们可以很容易地找到 A(n) 的最后五位数字。首先找到 A(100,000) MOD 100,000，我们可以通过乘法 mod 100,000 来简化此操作。请注意，A(200,000) MOD 100,000 只是 A(100,000)*A(100,000) MOD 100,000 因为 100,001 = 1 MOD 100,000 等等。所以 A(1,000,000,000,000) 只是 A(100,000)^10,000,000 MOD 1。

2,4,5,6,8,0 需要更加小心，您需要跟踪它们何时添加尾随零。显然，每当我们乘以以 2 或 5 结尾的数字时，我们最终会得到一个零。但是，在某些情况下，您可以获得两个零 25*4 = 100。

于 2014-06-18T09:20:42.547 回答