阶乘的非零尾数

你的名字 2023-02-12 06:00 169阅读 0赞

# 阶乘的非零尾数 #

--------------------

[链接][Link 1]

## 题面 ##

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

## 输入格式： ##

输入给出一个不超过  1 0 7 10^7 107  
的正整数 N 和要求输出的位数  0 < K < 10 0<K<10 0<K<10。

## 输出格式： ##

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

## 输入样例： ##

18 5

## 输出样例： ##

05728 3

## 思路 ##

*  求解**末尾零的个数**我们是比较熟悉的，一种方法是统计乘数因子中的**2的个数和5的个数，取两者中的最小值**即可，因为一对（2，5），两者相乘会增加一个0；另一种是边乘边对10取余，被取余次数就是尾部0的个数。
 *  对于第一个非零 K 位数，从K**比较小**（ 0 < K < 10 0<K<10 0<K<10），可知这里就是突破口。（这也是我们做题的经验，如果其他数值比较大，需要特别关注值比较小的数，一般就是解题的关键）因为相乘过程中溢出部分不会影响最后面的几位，所以只需要每次除了0（所以采用方式2统计末尾0的个数比较方便）只需保留相乘结果的后十几位(大于max\_K即可)。

## 代码 ##

#include <iostream>
    using namespace std;
    typedef long long LL;
    int main()
    {
        
        LL n,k;
        cin>>n>>k;
        LL mod = 1e15;
        LL ans = 1;
        LL cnt = 0;
        for(int i = 2; i <= n; ++i)
        {
        
            ans *= i;
            while(ans % 10 == 0)
            {
        
                cnt++;
                ans /= 10;
            }
            ans %= mod;
        }
        LL xx = ans;
        int a[15];
        int t = 0;
        while(k--)
        {
        
            a[t++] = xx%10;
            xx /= 10;
        }
        for(int i = t-1; i >= 0; i--)
            cout<<a[i];
         cout<<" "<<cnt<<endl;
        return 0;
    }

ps:

<table> 
 <thead> 
  <tr> 
   <th>类型</th> 
   <th>可以表示的最大数据</th> 
   <th>最大数据的位数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>int</td> 
   <td>2^31 -1 = 2147483647</td> 
   <td>10位</td> 
  </tr> 
  <tr> 
   <td>long long</td> 
   <td>2^63-1 = 9223372036854775807</td> 
   <td>19位</td> 
  </tr> 
  <tr> 
   <td>unsigned long long</td> 
   <td>2^64-1</td> 
   <td>20位</td> 
  </tr> 
 </tbody> 
</table>

[Link 1]: https://pintia.cn/problem-sets/1259839299727368192/problems/type/7