資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢滿足 n! % (k^x) = 0 的最大 x 值
假設我們有兩個整數 n 和 k。我們需要找到 x 的最大值，使得 n! mod (k^x) = 0。例如，當 n = 5，k = 2 時，輸出將為 3。因為 n! = 120，對於不同的 x 值，結果將是 -
120 mod 2^0 = 0, 120 mod 2^1 = 0, 120 mod 2^2 = 0, 120 mod 2^3 = 0, 120 mod 2^4 = 8, 120 mod 2^5 = 24, 120 mod 2^6 = 56, 120 mod 2^7 = 120。由於 x 的最大值為 3 時結果為 0，所以輸出為 3。
要解決這個問題，我們需要遵循以下步驟 -
- 計算 k 的平方根，並將其儲存到 m 中
- 對於 i := 2 到 m，執行以下步驟
- 當 i = m 時，將 i 設定為 k
- 如果 k 可以被 i 整除，則將 k 除以 i
- 執行一個迴圈到 n，並將商新增到一個名為 u 的變數中。
- 在每次迴圈後儲存 r 的最小值
示例
#include <iostream>
#include <cmath>
using namespace std;
int calculateMaxX(int n, int k) {
int result = n, v, u;
int m = sqrt(k) + 1;
for (int i = 2; i <= m && k > 1; i++) {
if (i == m) {
i = k;
}
for (u = v = 0; k % i == 0; v++) {
k /= i;
}
if (v > 0) {
int t = n;
while (t > 0) {
t /= i;
u += t;
}
result = min(result, u / v);
}
}
return result;
}
int main() {
int n = 5;
int k = 2;
cout<<"Maximum value of x is: " << calculateMaxX(n, k);
}輸出
Maximum value of x is: 3
更新於: 2019-12-18
157 次檢視
廣告