這題主要是去掉階乘末尾的0。是個(gè)老題了，編程之美中就有討論。因?yàn)?都是由2*5得來(lái)的。只要找出乘數(shù)中有多少個(gè)2*5對(duì)就行了。
因?yàn)?的個(gè)數(shù)遠(yuǎn)多于5，所以只要找出5的個(gè)數(shù)即可。因?yàn)閚最大為4220,5的個(gè)數(shù)為:
n/5+n/5/5+n/5/5/5+n/5/5/5/5+n/5/5/5/5/5+n/5/5/5/5/5/5;
然后再去除相應(yīng)數(shù)目的2。這樣剩下的數(shù)只需兩兩相乘后取最后一位即可。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream in("fact4.in");
ofstream out("fact4.out");
void?solve()
{
????int?n;
????in>>n;
????int?numof5?=?n/5+n/5/5+n/5/5/5+n/5/5/5/5+n/5/5/5/5/5+n/5/5/5/5/5/5;
????int?res?=?1;
????int?tmp;
????for(int?i=1;i<=n;++i){
????????tmp?=?i;
????????while(tmp%5==0)?tmp/=5;
????????while(tmp%2==0&&numof5!=0){
????????????tmp/=2;
????????????numof5--;
????????}
????????res*=tmp;
????????res%=10;
????}
????out<<res<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
原題：
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