题目描述
N 的阶乘(记作 N!)是指从 1 到 N(包括 1 和 N)的所有整数的乘积。
阶乘运算的结果往往都非常的大。
现在,给定数字 N,请你求出 N! 的最右边的非零数字是多少。
例如 5!=1×2×3×4×5=120,所以 5! 的最右边的非零数字是 2。
输入格式
共一行,包含一个整数 N。
输出格式
输出一个整数,表示 N! 的最右边的非零数字。
数据范围
1≤N≤1000
输入样例
7
输入样例
4
质因数分解
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1010;
LL primes[N], power[N];
bool st[N];
int n, cnt;
// 获取 n 以内的所有质数
void get_primes(int n) {
for (int i = 2; i <= n; i ++) {
if (!st[i]) {
primes[cnt ++] = i;
for (int j = i * 2; j <= n; j += i) st[j] = true;
}
}
}
// 得到每个数对应的幂
int get(LL n, LL p) {
int s = 0;
while (n) {
s += n / p;
n /= p;
}
return s;
}
// 高精度乘法
void mul(vector<LL> &a, int b) {
LL t = 0;
for (int i = 0; i < a.size(); i ++) {
a[i] = a[i] * b + t;
t = a[i] / 10;
a[i] %= 10;
}
while (t) {
a.push_back(t % 10);
t /= 10;
}
}
int main() {
cin >> n;
get_primes(n);
for (int i = 0; i < cnt; i ++) {
int p = primes[i];
power[p] = get(n, p);
}
vector<LL> res;
res.push_back(1);
// 把每个质数的幂求乘积
for (int i = 2; i <= n; i ++) {
while (power[i] --) mul(res, i);
}
reverse(res.begin(), res.end());
// 将结尾的 0 全部踢出
while (res.back() == 0) res.pop_back();
cout << res.back() <<endl;
return 0;
}