資料結構
聯網
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律研究在 C++ 中找出可整除某個階乘的最大數
假設我們有兩個數 n 和 fact。我們必須找出 n 的最大冪，該冪可以整除 fact! (fact 的階乘)。所以，如果 fact = 5，且 n = 2，那麼輸出將是 3。所以 5! = 120，這可以被 2^3 = 8 整除。
這裡我們將使用勒讓德公式。該公式可找出素數的最大冪，該冪可以整除 fact!。我們將找出 n 的所有素數因子，然後找出其可以整除 fact! 的最大冪。
所以，如果 fact 是 146，且 n = 15，那麼 n 的素數因子是 5 和 3。所以
對於 3，將是 [146/3] + [48/3] + [16/3] + [5/3] + [1/3] = 48 + 16 + 5 + 1 + 0 = 70。
對於 5，將是 [146/5] + [29/5] + [5/5] + [1/3] = 29 + 5 + 1 + 0 = 35。
示例
#include<iostream>
#include<cmath>
using namespace std;
int getPowerPrime(int fact, int p) {
int res = 0;
while (fact > 0) {
res += fact / p;
fact /= p;
}
return res;
}
int findMinPower(int fact, int n) {
int res = INT_MAX;
for (int i = 2; i <= sqrt(n); i++) {
int cnt = 0;
if (n % i == 0) {
cnt++;
n = n / i;
}
if (cnt > 0) {
int curr = getPowerPrime(fact, i) / cnt;
res = min(res, curr);
}
}
if (n >= 2) {
int curr = getPowerPrime(fact, n);
res = min(res, curr);
}
return res;
}
int main() {
int fact = 146, n = 5;
cout << "Minimum power: " << findMinPower(fact, n);
}輸出
Minimum power: 35
更新於:18-Dec-2019
205 次瀏覽
廣告