题解 P1134 【阶乘问题】

Radium_ · 2016-08-29 11:43:24 · 题解

个人觉得楼下方法没这个简单啊

其实我们可以在阶乘的时候不断去掉末尾的0

另外高位的乘法对低位没有影响，所以可以选一个数把高位取模丢掉

（利用竖式乘法，可以自己手算一下）

还是举个栗子吧

3*12=36
33*12=396
543*12=6516
//末尾都是一样的，由于只求末位，可以把2,33,543对10取模
//接下来原理类似
//末两位也可以拓展
333*12=3996
633*12=7596
1033*12=12396
//这里可以对100取模，反正结果一样，又不会溢出~~~

留名Radiumlrb

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll n,i,sum=1;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        sum*=i;
        while(sum%10LL==0LL) sum/=10LL;//去末尾的0 
        sum%=100000000LL;//竖式乘法原理，取个大点 不会超时 且不会溢出 的数
    }
    printf("%lld\n",sum%10);//末尾的数 
    return 0;
}