C ++中给定乘积的N个整数的最大GCD
假设我们有两个整数N和P。P是N个未知整数的乘积。我们必须找到这些整数的最大可能GCD。假设N = 3，且P = 24，则不同的组将像{1，1，24}，{1,2,12}，{1，3，8}，{1，4，6}，{2 ，2，6}，{2，3，4}。GCD为：1、1、1、1、2、1。因此，答案是2。
我们将找到P的所有素因子，并将它们存储到哈希映射中。当素数因子在所有整数中都相同时，N个整数将具有最大GCD。因此，如果P = p 1 k1 * p 2 k2 *…* p n kn。pi是主要因素。然后最大GCD将RES = P 1 K1 / N * P 2 K2 / N * ... * p Ñ KN / N。
示例
#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
long getMaxGCD(long N, long p) {
int gcd = 1;
unordered_map<int, int> prime_factors;
for (int i = 2; i * i <= p; i++) {
while (p % i == 0) {
prime_factors[i]++;
p /= i;
}
}
if (p != 1)
prime_factors[p]++;
for (auto v : prime_factors)
gcd = gcd * pow(v.first, v.second / N);
return gcd;
}
int main() {
long n = 3;
long p = 24;
cout << "MAX GCD: " << getMaxGCD(n, p);
}
输出结果
MAX GCD: 2
-
给定一个数N，我们如何求最大P*Q null 因此，暴力解决方案起作用。 再进一步，我们看到Q_max<=n/2，如果我们确实同意P =√n。 我们可以将我们的解决方案集细化为仅有那些值{P,n\2}，其中n\2>=√N。 这可能看起来微不足道，但它只是消除了可能的解决方案集的1/3。 我们是否可以添加其他聪明的程序来进一步减少设置？
-
我试着写一个代码，它接受一个介于1和1_000_000之间的整数，并返回一个比相同数字的整数大的最小整数，如果它不存在，则打印0。 举个例子 输入：156 输出165 输入330 输出0 输入27711 输出71127 我的问题是，下面的代码没有为其他输入返回正确的输出。 例如，在输入4231中，输出应该是4312。 我很难找到为每个输入返回正确输出的最佳算法。 TNX提前 }
-
本文向大家介绍在C ++中查找前N个质数的乘积，包括了在C ++中查找前N个质数的乘积的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个数字n。我们必须找到1到n之间的质数的乘积。因此，如果n = 7，则输出将为210，因为2 * 3 * 5 * 7 = 210。 我们将使用Eratosthenes筛分法来查找所有素数。然后计算它们的乘积。 示例 输出结果
-
给定N个数字，范围为-100.100。 要求重新排列元素以使产品价值之和最大。此任务中的乘积和定义为a1*a2+a2*a3..an-1*an 例如，给定数字10 20 50 40 30。 1,-2,3,-4,5,-6,7,-8,9,10,11,12,13,14,15,-16 预期的最大乘积为1342。 我的算法给出了下一个重排：
-
本文向大家介绍LCM的最大长度子数组等于C ++中的乘积，包括了LCM的最大长度子数组等于C ++中的乘积的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个数组A。我们必须找到子数组的最大长度，它的LCM与该子数组元素的乘积相同。如果找不到这种子数组，则返回-1。假设数组为{6，10，21}，则长度为2，因为在那里有子数组{10，21}，其LCM为210，乘积也为210。 该方法是直接的。我
-
假设第一个输入行是这样的： 第二输入线为： 输出应为： 我试着把所有的数字放在一个单独的数组里。但我不知道如何找到所说的数组的乘积。输出大小应该是第一个数的大小+第二个数的大小。因此，如果产品大小较小，它应该有一个前导0。