C ++中未知给定产品的最大GCD
假设我们有两个整数N和P。P是N个未知整数的乘积。我们必须找到这些整数的GCD。可能有不同的整数组，它们将给出相同的结果。在这里，我们将生成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。
我们喜欢的技术，假设g是1，a 2，…a n的GCD 。那么ai是g的倍数，而P是（a 1 * a 2 *…* a n）必须是g n的倍数。答案是max g，使得g n mod P =0。现在假设P = k1 p1 * k2 p1 *…* kn pn。g必须是这样的形式，然后要最大化g，我们必须选择p i = p i / N。
示例
#include <iostream> #include <cmath> using namespace std; long getMaxGCD(long n, long p) { int count = 0; long gcd = 1; while (p % 2 == 0) { p >>= 1; count++; //number of times P divided by 2 } if (count > 0) //if p has some 2s, then gcd = gcd* (long)pow(2, count / n); for (long i = 3; i <= sqrt(p); i += 2) { //check for all numbers after 2 count = 0; while (p % i == 0) { count++; p = p / i; } if (count > 0) { gcd = gcd* (long)pow(i, count / n); } } //如果最后的n是质数 if (p > 2) gcd = gcd* (long)pow(p, 1 / n); return gcd; } int main() { long n = 3; long p = 24; cout << "MAX GCD: " << getMaxGCD(n, p); }
输出结果
MAX GCD: 2
-
本文向大家介绍C ++中最大的回文产品，包括了C ++中最大的回文产品的使用技巧和注意事项，需要的朋友参考一下 假设我们输入了n，我们必须找到可以使用两个n位数相乘得到的最大回文。由于数字非常大，我们可以使用1337执行mod。因此，如果输入为2，则答案将为987，987 =（99 * 91）mod 1337 = 9009 mod 1337 = 987。 为了解决这个问题，我们将遵循以下步骤- m
-
本文向大家介绍最大产品子阵列| 在C ++中添加了否定产品案例，包括了最大产品子阵列| 在C ++中添加了否定产品案例的使用技巧和注意事项，需要的朋友参考一下 在本教程中，我们将讨论一个程序来查找具有负乘积情况的最大乘积子数组。 为此，我们将提供一个包含正值和负值的数组。我们的任务是在O(n)时间复杂度内找到子阵列的最大乘积。 示例 输出结果
-
本文向大家介绍C ++中给定乘积的N个整数的最大GCD，包括了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.过往实习经历深挖 3.实习困难与收获 4.怎么看待成人教育业务 5.知乎细分业务你更倾向/更适合哪个 二面 1.实习经历深挖 2.怎么看待增长产品 3.海内外做增长的不同 4.怎么看增长和商业化的关系 5.增长产品和体验产品角色换位，怎么推进原先的实习项目 6.作为产品负责人，体验和增长的PM发生矛盾，怎么解决 三面 1.怎么看自己的offer情况 2.从哪些角度综
-
本文向大家介绍用C ++中的给定操作构造最大堆栈的程序，包括了用C ++中的给定操作构造最大堆栈的程序的使用技巧和注意事项，需要的朋友参考一下 假设我们要制作一个最大的堆栈，它支持以下操作- MaxStk() 这将构造一个最大堆栈的新实例 push(val) 将val插入堆栈 top() 从堆栈中获取最高的元素 max() 从堆栈中获取最大元素 pop() 从堆栈中删除并返回最上面的元素 popm
-
本文向大家介绍C ++中给定数字最多的时间，包括了C ++中给定数字最多的时间的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个由4位数字组成的数组，那么我们必须找到最大的24小时制时间。我们知道最小的24小时时间是00:00，最大的时间是23:59。从00:00开始，如果自午夜起经过了更多时间，则时间会更大。我们必须以长度为5的字符串形式返回答案。如果没有有效的时间要返回，则返回一个空字符