2652 阶乘0的数量 V2 (二分)

给出一个数k,求最小的n,使得n的阶乘后面0的数量>=k。

例如k=1,

5的阶乘 = 12345 = 120,120后面有1个0。并且4的阶乘后面没有0,所以5是最小的结果。 输入 一个数k(1 <= k <= 10^9) 输出 输出最小的满足条件的n。 输入样例 1 输出样例 5 思路 :找最小的,用二分,另外 0 的个数和 阶乘中因子 5 的个数相等。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
const int MAX = 100005 ;
typedef long long LL ;
LL judge(LL x ) {
	LL ans = 0 ;
	while(x){
		x/=5 ;
		ans+=x;
	}
	return ans ; // 因子 5 的个数  , 因子 5 有多少个就能组成多少的 0 
	 
}
int main(){
	
	LL  n ;
	LL mid ;
	cin >> n ;
	LL l = 1 , r = 5*n ;
	for(int i = 0 ; i<33 ; i++ ) {
	    mid = (l+r) >>1 ;
	    // 最优的在左边, 统计的是最小的数字 
		if(judge(mid) >=n){
			r = mid ;
		}
		else {
			l = mid +1 ;
		}

	}
	cout<<mid ;
	
	return 0 ;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×