HELP: Factorials

[cOsMo]

I must find the last non zero digit of n!

Code: Select all

#include <cstdio>

int find_last(int x) {
	while (x%10==0) x/=10;
	return x%10;
}
int fact(int x) {
	int sol=1;
	for (int i=1;i<=x;i++)
		sol=find_last(find_last(i)*find_last(sol));
return sol;
}
int main(void)
{
	 int n;
	 scanf("%d",&n);
	 printf("%d\n",fact(n));
	 return 0;
}

I don't know what I did wrong...Plz help

[Krzysztof Duleba]

Your algorithm is wrong. 14! = 87178291200, 15! = 1307674368000.

[Dominik Michniewski]

use the following algorithm
1. Factorize n!
2. reduce power of 2 by power of 5 (reducing trailing zeroes)
3. observe that last digit of 2^x is
- 2^0 = 1, 2^1=2,2^2=4,2^3=8,2^4=6,2^5=2,2^6=4 .... so pattern is 24862486.... so last digit of 2^x is last digit of 2^(x%4)
- make the same steps for 3^x, 7^x ...
- observe that multiplying by 17 is the same (for last digit) like multiplying by 7 ... and so on

Best regards
DM

[cOsMo]

Thank you all. I totally misunderstood the problem.