7-7 阶乘的非零尾数 (20分)

  • 时间:
  • 浏览:
  • 来源:互联网

“求 N 阶乘末尾的第一个非零数字”是一道常见的企业笔试题。这里我们略微做个变化,求 N 阶乘末尾的第一个非零 K 位数,同时输出末尾有多少个零。

输入格式:
输入给出一个不超过 10
​7
​​ 的正整数 N 和要求输出的位数 0<K<10。

输出格式:
在一行中输出 N 阶乘末尾的第一个非零 K 位数(注意前导零也要输出)、以及末尾 0 的个数,其间以 1 个空格分隔。

输入样例:
18 5

输出样例:
05728 3

用到的知识点:
1.前缀加零法!
2.后缀去零法!

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 10;
char g[N][N];
int cnt = 0;
typedef long long LL;
//前缀有零的添加法!
void write(int ans, int st, int ed)
{
    if(st == ed) return;
    write(ans / 10, st + 1, ed);
    putchar(ans % 10 + '0');
}

int main()
{
    int n, k, cnt = 0;
    cin >> n >> k;
    LL ans = 1, mod = pow(10, k);
    for(int i = 1; i <= n; i ++ )
    {
        ans *= i;
        //后缀有零的去除法!
        while(ans % 10 == 0)
        {
            ans /= 10;
            cnt ++ ;
        }
        ans %= mod;
    }
    write(ans, 0, k);
    cout << ' ' << cnt << endl;
    return 0;
}

本文链接http://element-ui.cn/news/show-341891.aspx