数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告