함수 f(x)가 있다고 가정하면 x의 계승 끝에 0의 수를 반환합니다. 따라서 f(3) =0인 경우 3! =6은 끝에 0이 없지만 f(11) =2는 11! =39916800은 끝에 2개의 0이 있습니다. 이제 K가 있을 때 f(x) =K라는 속성을 갖는 음이 아닌 정수 x가 몇 개인지 찾아야 합니다.
따라서 입력이 K =2와 같으면 답은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ok() 함수를 정의하면 x가 걸립니다.
- ret :=0
- 초기화 i :=5의 경우, i <=x, 업데이트 i :=i * 5, −
- ret :=ret + x / i
- 반환
- 메인 방법에서 다음을 수행하십시오. -
- K가 0과 같으면 -
- 반환 5
- 낮음 :=1, 높음 :=K * 5
- 낮은 <높은 동안 −
- 중간 :=낮음 + (높음 - 낮음) /2
- x :=ok(중간)
- x
- 낮음 :=중간 + 1
- 그렇지 않으면
- 높음 :=중간
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli ok(lli x){
int ret = 0;
for(lli i = 5; i <= x; i *= 5){
ret += x / i;
}
return ret;
}
int preimageSizeFZF(int K) {
if(K == 0) return 5;
lli low = 1;
lli high = (lli)K * 5;
while(low < high){
lli mid = low + (high - low) / 2;
lli x = ok(mid);
if(x < K){
low = mid + 1;
}else high = mid;
}
return ok(low) == K ? 5 : 0;
}
};
main(){
Solution ob;
cout << (ob.preimageSizeFZF(2));
} 입력
2
출력
5