设 x 和 y 为两个数字。在这种情况下，如果当 y 除以 x 时返回零余数，则称 x 是 y 的除数。区间中出现的最大除数是该区间最大元素数的除数。
问题陈述
给定一个区间 [a, b]。找出包含 a 和 b 的范围内（除了“1”之外）出现的最大除数。如果所有除数出现次数相同，则返回 1。
示例 1
Input [2, 5]
Output 2
解释 – 2 的约数 = {1, 2}，3 的约数 = {1, 3}，4 的约数 = {1, 2, 4}，5 的约数 = {1 , 5}。 2 是出现次数最多的除数。
示例 2
Input [2, 5]
Output 2
解释 – 2 的约数 = {1, 2}，3 的约数 = {1, 3}，4 的约数 = {1, 2, 4}，5 的约数 = {1 , 5}。 2 是出现次数最多的除数。
方法 1：暴力破解
解决该问题的强力方法是找到区间内所有数字的所有约数，并将它们连同出现的次数一起存储在映射中。
算法
过程除数（num）
对于 i = 1 到 n1/2+1
如果 num%i == 0
如果 num/i == i
如果 i 不在地图中，则插入 (i, 1)
否则映射[i]++
其他
如果 i 不在地图中，则插入 (i, 1)
否则映射[i]++
如果 num/i 不在地图中，则插入 (num/i, 1)
其他地图[num/i]++
过程 maxDivisors (a, b)
对于 n = a 到 b
除数 (n)
map.erase(1)
除数 = 1，计数 = int_min
对于地图中的每个元素
if it.value > 计数
计数 = it.value
除数 = it.key
示例：C++ 实现
在下面的程序中，我们在 divisors() 函数中查找每个数字的约数，并在 maxdivisor() 函数中查找最大出现的除数。
#include using namespace std;// map storing occurrence of each divisorunordered_map occ;// function to find all the divisors of a number and store it in mapvoid divisors(int num){ for (int i = 1; i <= (sqrt(num) + 1); i++) { // checking if i is divisor of num if (num % i == 0) { // checking if num has identical divisors i.e. if i*i == num // if identical divisors then save only one if (num / i == i) { if (occ.find(i) == occ.end()) { occ.insert(make_pair(i, 1)); } else{ occ[i]++; } } else{ // saving divisor i if (occ.find(i) == occ.end()) { occ.insert(make_pair(i, 1)); } else{ occ[i]++; } // saving the divisor of num corresponding to i if (occ.find(num / i) == occ.end()) { occ.insert(make_pair(num / i, 1)); } else{ occ[num / i]++; } } } }}// function to find maximum occurring divisor in an intervalint maxDivisor(int a, int b){ for (int n = a; n second > cnt) { cnt = it->second; div = it->first; } } return div;}int main(){ int a = 4, b = 7; cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = "; cout << maxDivisor(a, b); return 0;}
输出
For the interval [4, 7] maximum occurring divisor = 2
时间复杂度 – O(n3/2)，因为对于区间中的每个数字，为了查找除数，执行复杂度为 O(n1/2) 的循环。
空间复杂度 – O(n)，地图空间。
方法 2
可以通过减少用每个除数的出现来填充映射的时间来进一步优化上述方法。不是找到每个数字的除数，而是可以通过计算区间的下限和上限来获知区间中每个除数的出现情况。
让我们以区间 [2, 5] 为例。
可能的约数集是从 1 到 5。因此，出现 1 = 5/1 – 2/1 +1 = 4。出现 2 = 5/2 – 2/2 + 1 = 2。出现 3 = 5/3 – 2/3 = 1。出现 4 = 5/4 – 2/4 = 1。出现 5 = 5/5 – 2/5 = 1。
以上可以形式化为，
如果下界%除数 == 0 则 occ = 上界/除数 – 下界/除数 + 1
其他 occ = 上界/除数 – 下界/除数
算法
过程 maxDivisor (a, b)
对于 i = 2 到 b
如果 a%i == 0
次数 = b/i – a/i +1
其他
次数 = b/i – a/i
map.insert(i, 次)
除数 = 1，计数 = int_min
对于地图中的每个元素
if it.value > 计数
计数 = it.value
除数 = it.key
示例：C++ 实现
在下面的程序中，我们不是按相反的顺序查找数字的除数，而是针对每个除数查找它在区间内有多少个倍数。
#include using namespace std;// function to find maximum occurring divisor in an intervalint maxDivisor(int a, int b){ // map used to store occurrences of divisors unordered_map occ; for (int i = 2; i second > cnt){ cnt = it->second; div = it->first; } } return div;}int main(){ int a = 1, b = 10; cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = "; cout << maxDivisor(a, b); return 0;}
输出
For the interval [1, 10] maximum occurring divisor = 2
方法 3
该问题的一个非常简单的解决方案如下所示，
在任何大小 > 1 的区间中，一半的数字（每个偶数）将以 2 作为除数。
因此可以如下使用。
算法
过程 maxDivisors (a, b)
如果 a == b
ans = a
其他
ans = 2
示例：C++ 实现
在下面的程序中，我们实现了每个偶数都有 2 作为约数的观察结果。
#include using namespace std;// function to find the maximum occurring divisor in an intervalint maxDivisor(int a, int b){ if (a == b){ return a; } else { return 2; }}int main(){ int a = 1, b = 10; cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = "; cout << maxDivisor(a, b); return 0;}
输出
For the interval [1, 10] maximum occurring divisor = 2
结论
总之，为了找到一个区间内最大出现除数，我们可以使用上述方法，时间范围从 O(n3/2) 到 O(1)，空间范围从 O(n) 到 O( 1).
以上就是在一个区间内的最大公约数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444188.html
微信扫一扫 
支付宝扫一扫 
