AcWing 1381. 阶乘
原题链接
简单
作者:
acw_weian
,
2021-01-27 21:11:03
,
所有人可见
,
阅读 516
/**
* a * b % c = a % c * b % c
* n! = 2^α1 * 5^α2 * ... * pαk
*
* 时间复杂度 O(n * (log2n + log5n) ) log2n中的2是底数 同理log5n
*/
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = 1, d2 = 0, d5 = 0;
for(int i = 1; i <= n; i++){
int t = i;
while(t % 2 == 0){
d2++;
t /= 2;
}
while(t % 5 == 0){
d5++;
t /= 5;
}
res = res * t % 10;
}
int k = Math.min(d2, d5);
for(int i = 0; i < d2 - k; i++) res = res * 2 % 10;
for(int i = 0; i < d5 - k; i++) res = res * 5 % 10;
System.out.println(res);
}
}