2187: 阶乘新问题

解题思路:

末尾的0都是由2和5相乘得到的，举几个例子：

  40=2^3*5^1 只有一个5和2对应，所以只有一个0

500=2^2*5^3 只有两个2和5对应，所以只有两个0

也就是说，末尾的0的个数就是2和5指数中最小的指数

我们只需要进行质因数分解就可以了，很容易知道，在阶乘里面2出现的次数是远大于5的，所以只需要找到5出现的次数就可以了。

需要注意的是，这道题不是n的阶乘是1-n的阶乘，需要两次循环，外重循环1-n，内循环表示i的阶乘，这样时间复杂度是很大的。

所以有了这样一个式子：z+=(n-i+1)*k;
举例 n=7  s=1！*2！*3！*4！*5!*6!*7!

在5！的时候k=1，那么后面的6！ 7！也会有一个5，所以最后是3个5 末尾3个0

参考代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
  
#define ll long long
  
int main(){
    ll i;
    ll n,m=0,k=0,z=0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        m=i;
        k=0;
        while(m%5==0){
            k++;
            m/=5;
        }
        z+=(n-i+1)*k;
    }
    printf("%lld",z);
      
    return 0;
}

对应这道题的还有二进制末尾0的问题，不过我在dotcpp上没有找到类似问题，就在这里写一下当扩展吧。

二进制末尾0我们可以用右移判断最低位是否为1来进行，例如：

12（1100）=2^2*3，末尾有两个零。

14（1110）=2^1*7，末尾有一个零。

如果一个数的二进制最低位为1的话，他一定是一个奇数，奇数的因子里面一定没有2，所以做右移除2就相当于把一个数的因子2全部找出来，最后让这个数成为一个奇数。

所以二进制末尾0个数==因子2的个数。

这样时间复杂度为log n，不过一般这样的问题都是很多数相乘问题，最后的答案不能用变量表达出来。

所以我们只需要对输入的数进行分解，找到所有因子2的次数，就是答案了。