在一个区间内的最大公约数

设 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 <bits/stdc++.h>
using namespace std;

// map storing occurrence of each divisor
unordered_map<int, int> occ;

// function to find all the divisors of a number and store it in map
void 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 interval
int maxDivisor(int a, int b){
   for (int n = a; n <= b; n++){
      divisors(n);
   }
   
   // deleting all occurrences of 1 as 1 is not to be returned until the interval is [1,1]
   occ.erase(1);
   
   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++) {
      if (it->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 <bits/stdc++.h>
using namespace std;

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){

   // map used to store occurrences of divisors
   unordered_map<int, int> occ;
   for (int i = 2; i <= b; i++){
      int times;
      if (a % i == 0){
         times = (b / i) - (a / i) + 1;
      }
      else{
         times = (b / i) - (a / i);
      }
      occ.insert(make_pair(i, times));
   }

   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++){
      if (it->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 <bits/stdc++.h>
using namespace std;

// function to find the maximum occurring divisor in an interval
int 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).

以上是在一个区间内的最大公约数的详细内容。更多信息请关注PHP中文网其他相关文章！