阶乘分解 && 边输入边处理
#include<iostream>
using namespace std;
auto main() -> int
{
int n; cin >> n;
int d2 = 0, d5 = 0, res1 = 1;
for(int i = 1; i <= n; ++i)
{
int x = i;
while(x % 2 == 0) x/=2, d2++;
while(x % 5 == 0) x/=5, d5++;
res1 = res1 * x % 10;
}
int m = min(d2, d5);
for(int i = 0; i < d2 - d5; ++i) res1 = res1 * 2 % 10;
for(int i = 0; i < d5 - m; ++i) res1 = res1 * 5 % 10;
cout << res1 << endl;
}
题目思路分析
首先通过题目给出的 N 最多为 1000 , 1000的阶乘有2000多位,故这里并不能使用直接从个位遍历的方式.故正确的思路,首先题目要找的是最右边第一个非0的数字,然而我们知道要产出0这个位数,如果将阶都分解,则是5和2这两个数相乘, 例如将 N!分解成 m个2 和 n 个5 和 一个X相乘。然后比较m 和 n 的大小,然后取小的 k = min(m,n); 则此时说明这个阶乘有 k 个 0, 除去某尾的0, 剩下的数为 (m - k) * 2 * X. 然后取%10即为答案,这里 有个关系 (a * b) % c = a % c * b % c, 故可以做到变算边取余, 防止数据溢出。 这里其实可以不用判断m和n的大小,肯定存在 m >= n;