Factorials
The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.
PROGRAM NAME: fact4
INPUT FORMAT
A single positive integer N no larger than 4,220.
SAMPLE INPUT (file fact4.in)
7
OUTPUT FORMAT
A single line containing but a single digit: the right most non-zero digit of N! .
SAMPLE OUTPUT (file fact4.out)
4
Analysis
Considering the small amount of 4,220, we can find that the highest number of zeros is 5 since 5^5<4,220<5^6. What we are interested in is the last 6 numbers after each step of factorial. At last, we may output the last non-zero digit.
Code
/**//*
ID:braytay1
PROG:fact4
LANG:C++
*/
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream fin("fact4.in");
ofstream fout("fact4.out");
int n;
int s;
fin>>n;
s=1;
for (int i=1;i<=n;i++){
s*=i;
if (s>=100000&&s%10==0) {
while (s%10==0)
s/=10;
s%=100000;
}
else s%=100000;
}
while (s%10==0)
s/=10;
fout<<s%10<<endl;
return 0;
}