【二分】阶乘0的数量

「爱情、让人受尽委屈。」 2024-03-22 09:43 64阅读 0赞

**一发过！**

[题目-阶乘0的数量 V2 (51nod.com)][-_0_ V2 _51nod.com]

题意：

![af9dd1bd12db4fe784d72a9da4aa1f57.png][]

思路：

首先是个常识：一个数结尾0的个数取决于(2,5)这一对的个数，即5这个因子的个数

然后注意特殊性，1e9个0，说明不能算出来

然后n越大，阶乘里的0的个数就越多，所以满足二段性，所以可以二分

统计阶乘中因子p的个数可以这样算：n/p的个数，n/(p\*p)的个数....这样加起来就好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e7+10;
    const int mxe=1e7+10;
    const int Inf=1e9;
    
    int k,ans;
    
    bool check(int x){
    	int res=0;
    	while(x){
    		res+=x/5;
    		x/=5;
    	}
    	return res>=k;
    }
    void solve(){
    	cin>>k;
    	int l=1,r=1e18;
    	while(l<=r){
    		int mid=l+r>>1;
    		if(check(mid)){
    			ans=mid;
    			r=mid-1;
    		}else l=mid+1;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[-_0_ V2 _51nod.com]: http://www.51nod.com/Challenge/Problem.html#problemId=2652
[af9dd1bd12db4fe784d72a9da4aa1f57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/e6e40cfa58564d14ae42bb8f0f0e2db7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，64人围观）

还没有评论，来说两句吧...

相关阅读

相关【二分】阶乘0的数量

一发过！ [题目-阶乘0的数量 V2 (51nod.com)][-_0_ V2 _51nod.com] 题意： ![af9dd1bd12db4fe784d72a9da4a

「爱情、让人受尽委屈。」/ 2024年03月22日 09:43/ 0 赞/ 65 阅读

相关 51nod1003 阶乘后面0的数量

[1003 阶乘后面0的数量][1003 _0] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [1003 _0]: http:

落日映苍穹つ/ 2024年02月17日 22:56/ 0 赞/ 49 阅读

相关阶乘

function fn(num) { return(function infn(num) { if (num <= 1

た入场券/ 2023年06月03日 15:59/ 0 赞/ 541 阅读

相关阶乘尾部0的个数

阶乘尾部0的个数输入输入数据有若干行，每行上有一个非负整数n，对应一种情形。输出对于每一种情形，直接输出结果、换行。样例输入 8 16

素颜马尾好姑娘i/ 2023年03月04日 06:54/ 0 赞/ 33 阅读

相关阶乘末尾0的数量（C++牛客网）

解题思路：（1）5、25、125......的倍数 class Solution { public: / the nu

旧城等待，/ 2023年01月13日 09:28/ 0 赞/ 155 阅读

相关基础算法题——求单链表结点的阶乘和（0的阶乘(0!) 是1、1的阶乘(1!) 是1）

[求单链表结点的阶乘和][Link 1] ![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

傷城~/ 2022年12月20日 02:23/ 0 赞/ 150 阅读

相关 NYOJ 84 阶乘的0

阶乘的0 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述计算n!的十进制表示最后有多少个0 输入第一行输入一个整数N表示测试

红太狼/ 2022年09月19日 10:36/ 0 赞/ 166 阅读

相关 51Nod--1003 阶乘后面0的数量

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1003][http_www.51nod

「爱情、让人受尽委屈。」/ 2022年06月15日 11:45/ 0 赞/ 159 阅读

相关 nyoj-84-阶乘的0

阶乘的0 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述计算n!的十进制表示最后有多少个0 输入第一行输入一个整数N表示

朴灿烈づ我的快乐病毒、/ 2022年05月27日 06:46/ 0 赞/ 171 阅读

相关阶乘

问题描述　　一个整数n的阶乘可以写成n!，它表示从1到n这n个整数的乘积。阶乘的增长速度非常快，例如，13!就已经比较大了，已经无法存放在一个整型变量中；而35!就更大了

雨点打透心脏的1/2处/ 2022年04月10日 06:42/ 0 赞/ 318 阅读