让阶乘程序更快？

Question

我一直想把这个提交给一个有编程课程的网站，但是法官一直告诉我这个程序执行时间太长了:/

问题陈述：

Write a program that reads a non-negative integer n from the standard input, will count the digit of tens and the digit of ones in the decimal notation of n!, and will write the result to the standard output. In the first line of input there is one integer D (1≤D≤30), denoting the number of cases to be considered. For each case of entry. your program should print exactly two digits on a separate line (separated by a single space): the tens digit and the ones digit of n! in the decimal system.

Input/Output:

Input	Output
2
1	0 1
4	2 4

#include <iostream>

using namespace std;

int d,n;

int main()
{
    cin>>d;
    for(int i=0; i<d; i++)
    {
        cin>>n;
        int silnia = 1;
        for(int j=n; j>1; j--)
        {
            silnia=silnia*j;
        }
        if(silnia == 1) cout<<0<<" "<<silnia<<"\n";
        else cout<<(silnia/10)%10<<" "<<silnia%10<<"\n";
    }
    return 0;
}

Answer 1

您可以摆脱 内部循环 因为 n! == (n - 1)! * n:

  cin >> d;

  int factorial = 1;

  cout << 0 << " " << 1 << "\n";

  for (int i = 1; i < d; ++i) {
    /* we operate with last two disgits: % 100 */
    factorial = (factorial * i) % 100;

    cout << factorial / 10 << " " << factorial % 10 << "\n";
  }

编辑：另一个问题是

  silnia=silnia*j;

行。阶乘 增长快:

  13! = 6227020800 > LONG_MAX (2147483647)

这就是为什么我们应该使用 模运算：我们保留的不是阶乘本身（可能非常大），而是它的最后两位数字（注意 % 100），保证在 00..99 范围内：

  factorial = (factorial * i) % 100;

甚至（如果i可以很大）

  factorial = (factorial * (i % 100)) % 100;

Answer 2

由于只需要 n! 的最后 2 位数字，任何 n >= 10^** 都会有一个 n! 和 00 作为最后 2 位数字。

一个捷径是测试n：这把问题从O(n)带到了O(1)。

  int factorial = 0;
  if (n < 10) {
    int factorial = 1;
    for(int j=n; j>1; j--)
    {
        factorial *= j;
    }
    factorial %= 100;
  }

或者在 [0...10) 范围内对 n 使用查找 table 以删除 for 循环。

---

^**10_or_more！里面有一个 2 * 5 * 10 * other factors。然后所有这些阶乘都以 00.

结尾

让阶乘程序更快？

Making a factorial program faster?

c++

optimization

factorial