C++ 在区间中出现最多的除数

设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：蛮力法

问题的蛮力方法是找出区间内所有数字的除数，并将它们存储在一个映射中，同时保存它们的出现次数。

步骤

过程divisors（num）

• 对于i从1到n的开方+1

• 如果num%i == 0

• 如果num/i == i

• 如果i不在映射中则插入（i，1）

• 否则map[i]++

• 否则

• 如果i不在映射中则插入（i，1）

• 否则map[i]++

• 如果num/i不在映射中则插入（num/i，1）

• 否则map[num/i]++

过程maxDivisors（a，b）

• 对于n从a到b

• divisors（n）

• map.erase（1）

• divisor = 1，count = int_min

• 对于映射中的每个元素it

• 如果it.value > count

• count = it.value

• divisor = 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)，map的空间。

方法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

• times = b/i – a/i + 1

• 否则

• times = b/i – a/i

• map.insert(i, times)

• divisor = 1, count = int_min

• 对于 map 中的每个元素 it

• 如果 it.value > count

• count = it.value

• divisor = 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)不等。