Algorithm

USACO Section3.2 fact4

Problem Summary

Given N, find the last digit of N! that is not zero.

Solution

The solution is obvious once we notice that,

  1. Only 2 and 5 as a pair can cause 0 at the end of the product,
  2. There are always more 2s than 5s in a factorial.

So we firstly ignore the 2s and 5s during the calculation, and get the number of 2s and 5s respectively, then multiply the result by the extra 2s.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,ans=1;
int main()
{
	fstream fin("fact4.in",ios::in);
	fstream fout("fact4.out",ios::out);
	fin>>n;
	int j;
	int c2=0,c5=0;
	for(int i=2;i<=n;i++)
	{
		j=i;
		while(j>0 && (j&1)==0) { j>>=1; c2++; }
		while(j>0 && j%5==0) { j/=5; c5++; }
		ans=ans*j%10;
	}
	c2-=c5;
	while(c2)
	{
		ans=(ans<<1)%10;
		c2--;
	}
	
	fout<<ans<<endl;
	
	fin.close();
	fout.close();
	return 0;
}