資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中找到最小的數 X，使得 X！包含至少 Y 個尾隨零
我們必須取一個數 Y，我們將找到最小的數 X，使得 X！包含至少 Y 個尾隨零。例如，如果 Y = 2，則 X = 10。因為 X! = 3228800。它有 Y 個零。
我們可以使用二分查詢來解決這個問題。N! 中尾隨零的個數由 N! 中因子 5 的個數給出。可以在範圍 [0, 5*Y] 中使用二分查詢找到 X
示例
#include<iostream>
using namespace std;
int factorCount(int n, int X) {
if (X < n)
return 0;
return (X / n + factorCount(n, X / n));
}
int findX(int Y) {
int left = 0, right = 5 * Y;
int N = 0;
while (left <= right) {
int mid = (right + left) / 2;
if (factorCount(5, mid) < Y) {
left = mid + 1;
}else {
N = mid;
right = mid - 1;
}
}
return N;
}
int main() {
int Y = 4;
cout << "Smallest value of X: " << findX(Y);
}輸出
Smallest value of X: 20
更新於：2019 年 11 月 4 日
82 次瀏覽
廣告