AcWing 1381. 阶乘

N 的阶乘(记作 N!)是指从 1 到 N(包括 1 和 N)的所有整数的乘积。

阶乘运算的结果往往都非常的大。

现在,给定数字 N,请你求出 N! 的最右边的非零数字是多少。

例如 \(5!=1×2×3×4×5=120\),所以 5! 的最右边的非零数字是 2。

输入格式
共一行,包含一个整数 \(N\)

输出格式
输出一个整数,表示 N! 的最右边的非零数字。

数据范围
\(1≤N≤1000\)

输入样例:
7
输出样例:
4

此题来源于:Usaco training 3.2

刚看到这题的时候吓了一跳,想了下用高精度来模拟,结果发现并不需要就能得到答案, 由 \((a\ *\ b)\ \%\ p\ \equiv\ (a\ \%\ p\ *\ b\ \%\ p)\ \%\ p\)处理后, 就能保证\(N!\)保持在int数据范围内。

思路:因为结果中右边的0都是由10组成的,已知\(10 = 2^1 * 5^1\),分解质因数后\(N!\ =\ 2^\alpha\ *\ 5^\beta\ *\ p_1^{\beta2}\ *\ p_2^{\beta3}\ *\ ...\ *\ p_n^{\beta n}\),那么去掉所有0的话只需要去掉所有\(2^{min(\alpha,\ \beta)}\ *\ 5^{min(\alpha,\ \beta)}\)即可。

AC代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;

constexpr int MAXN = 27, MAXM = 1e4 + 5;
int n, d2, d5;      //d2统计质因子2的个数,d5统计质因子5的个数

int main(){
	cin >> n;
	int ans = 1;
	for(int i = 2; i <= n; ++ i){
		
		int t = i;
		while(t % 2 == 0)
			t /= 2, d2 ++;
		while(t % 5 == 0)
			t /= 5, d5 ++;
		ans = ans * t % 10;
	}
	int k = min(d2, d5);
	for(int i = 0; i < d2 - k; ++ i)      //乘上被多除掉的2
		ans = ans * 2 % 10;
	for(int i = 0; i < d5 - k; ++ i)      //乘上被多除掉的5
		ans = ans * 5 % 10;
	cout << ans << ‘\n‘;
	
	return 0;
}

AcWing 1381. 阶乘

上一篇:重学c#————struct


下一篇:用游标遍历某台服务器下所有的数据库中 汲及到某个关键词的 所有存储过程及自定义函数