c - Project Euler Number 160 - C 语言尝试

Question

如果我有点傻，请原谅我，但我只是最近才开始编程，在 Project Euler 上做第 160 题可能有点力不从心。我已尝试解决它，但似乎在任何个人计算机上处​​理 1tn 个数字都会花费太长时间，所以我想我应该研究数学以找到一些捷径。

欧拉计划问题 160:

For any N, let f(N) be the last five digits before the trailing zeroes in N!. For example,

9! = 362880 so f(9)=36288 10! = 3628800 so f(10)=36288 20! = 2432902008176640000 so f(20)=17664

Find 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);
}

Answer 1

问题是:

For any N, let f(N) be the last five digits before the trailing zeroes in N!. Find f(1,000,000,000,000)

让我们改一下问题:

For any N, let g(N) be the last five digits before the trailing zeroes in N. For any N, let f(N) be g(N!). Find 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 大得多。