I've been trying to submit this to a website with programming lessons, but the judge keeps telling me that this program takes too long to execute :/

Problem Statement:

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:

#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;
}

CodePudding user response：

You can get rid of inner loop since 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";
  }

Edit: Another issue is with

  silnia=silnia*j;

line. Factorial grows fast:

  13! = 6227020800 > LONG_MAX (2147483647)

that's why we should use modulo arithmetics: we keep not factorial itself (which can be very large), but its two last digits (note % 100), which is garanteed to be in 00..99 range:

  factorial = (factorial * i) % 100;

Or even (if i can be large)

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

CodePudding user response：

Since only the last 2 digits of n! are needed, any n >= 10^** will have a n! with 00 as the last 2 digits.

A short-cut is to test n: This takes the problem from O(n) to O(1).

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

Or use a look-up table for n in the [0...10) range to drop the for loop.

---

^** 10_or_more! has a 2 * 5 * 10 * other factors in it. All these factorials then end with 00.