【牛客】CD56 有关阶乘的两个问题1：给定一个非负整数N，返回N!结果的末尾为0的数量

谁借莪１个温暖的怀抱￠ 2022-09-11 08:11 106阅读 0赞

以10！为例
    	1*2*3*4*5*6*7*8*9*10
    =	1*2*3*4*5*6*7*8*9*2*5
    其实就是 因子里面2*5的对数
    但是对于任意的阶乘，因子里面5的个数肯定是少于2的
    因为因子2 每隔2个至少有一个，有时候还多于两个因子2
    所以直接数5的数量就可以了
    当然可以遍历 计算5的倍数中有几个5的因子 然后加起来
    但是最大的数据有10^18
    所以只能采用log的做法
    
    以75！为例 我们只关注因子里面有 5的

对于 5*5=25 以及 5*5*2 以及 5*5*3 都是有2个因子5
    同理 5*5=125 以及 5*5*5*2 以及 5*5*5*3 都是有3个因子5
    所以就可以计算 n/5 得到n里面至少有1个5的数字有多少个（包含大于1个5的数组 例如25）
    算 n/25 得到n里面至少有2个5的数字有多少个（包含大于2个5的数组 例如125）
    。。。。
    最后 如果5*5*5*5...超过了n就不需要计算了

复杂度  O ( l o g 5 n ) O(log\_\{5\}n) O(log5n)

#include<iostream>
    
    using namespace std;
    
    using ll = long long;
    
    ll sol(ll n){ 
        
        ll sub = 5;
        ll ret = n/sub;
        sub = 25;
        while(sub<=n){ 
            ret += n/sub;
            sub*=5;
        }
        return ret;
    }
    
    int main(){ 
        ll n;
        cin>>n;
        cout<<sol(n)<<endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBARFVUX0xZSA_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBARFVUX0xZSA_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ee54e03928194170a9b125cb7e7684b1.png