检查给定的两个数字是否为亲和数

---

亲和数 − 根据数论，亲和数是具有相同丰度指数的两个或多个数。

丰度指数 − 自然数的丰度指数可以定义为自然数的所有约数之和与自然数本身的比率。

数字 n 的丰度可以表示为 $\mathrm{\frac{\sigma(n)}{n}}$，其中 $\mathrm{\sigma(n)}$ 表示约数函数，等于 n 的所有约数。

例如，自然数 30 的丰度指数为：

$$\mathrm{\frac{\sigma(30)}{30}=\frac{1+2+3+5+6+10+15+30}{30}=\frac{72}{30}=\frac{12}{5}}$$

如果存在一个数 m ≠ n，使得

$\mathrm{\frac{\sigma(m)}{m}=\frac{\sigma(n)}{n}}$

则称数字 n 为“亲和数”。

问题陈述

给定两个数字 Num1 和 Num2。返回这两个数字是否为一对亲和数。

示例 1

Input: Num1 = 30, Num2 = 140

Output: Yes

解释

$$\mathrm{\frac{\sigma(30)}{30}=\frac{1+2+3+5+6+10+15+30}{30}=\frac{72}{30}=\frac{12}{5}}$$

$$\mathrm{\frac{\sigma(140)}{140}=\frac{1+2+4+5+7+10+14+20+28+35+70+140}{140}=\frac{336}{140}=\frac{12}{5}}$$

由于 \frac{\sigma(30)}{30}=\frac{\sigma(140)}{140}，因此 30 和 140 是一对亲和数。

示例 2

Input: Num1 = 5, Num2 = 24

Output: No

解释

$$\mathrm{\frac{\sigma(5)}{5}=\frac{1+5}{5}=\frac{6}{5}}$$

$$\mathrm{\frac{\sigma(24)}{24}=\frac{1+2+3+4+6+8+12+24}{24}=\frac{60}{24}=\frac{15}{6}}$$

由于 $\mathrm{\frac{\sigma(5)}{5}\neq\frac{\sigma(24)}{24}}$，因此 5 和 24 不是一对亲和数。

方法 1：暴力法

该问题的暴力解决方案首先是找到两个数字的所有约数之和，然后计算两者的丰度指数值，并进行比较以获得结果。

伪代码

procedure sumOfDivisors (n)
   sum = 0
   for i = 1 to n
      if i is a factor of n
         sum = sum + i
      end if
   ans = sum
end procedure

procedure friendlyPair (num1, num2)
   sum1 = sumOfDivisors (num1)
   sum2 = sumOfDivisors (num2)
   abIndex1 = sum1 / num1
   abIndex2 = sum2 / num2
   if (abIndex1 == abIndex2)
      ans = TRUE
   else
      ans = FALSE
   end if
end procedure

示例：C++ 实现

在下面的程序中，计算所有约数的和以找到丰度指数。

#include <bits/stdc++.h>
using namespace std;

// Function to find sum of all the divisors of number n
int sumOfDivisors(int n){
   int sum = 0;
   for (int i = 1; i <= n; i++){
      if (n % i == 0){
         sum += i;
      }
   }
   return sum;
}
// Function to find if two numbers are friendly pairs or not
int friendlyPair(int num1, int num2){

   // Finding the sum of all divisors of num1 and num2
   int sum1 = sumOfDivisors(num1);
   int sum2 = sumOfDivisors(num2);
   
   // Calculating the abundancy index as the ratio of the sum of divisors by the number
   int abIn1 = sum1 / num1, abIn2 = sum2 / num2;
   
   // Friendly pair if the abundancy index of both the numbers are same
   if (abIn1 == abIn2){
      return true;
   }
   return false;
}
int main(){
   int num1 = 30, num2 = 140;
   cout << num1 << " and " << num2 << " are friendly pair : ";
   if (friendlyPair(num1, num2)){
      cout << "YES";
   }
   else{
      cout << "NO";
   }
   return 0;
} 

输出

30 and 140 are friendly pair : YES

时间复杂度 − O(n)，因为 sumOfDivisors() 函数遍历一个循环

空间复杂度 − O(1)

方法 2：丰度指数的简化形式

可以通过将分子和分母除以最大公约数来找到丰度指数的简化形式。然后，通过检查两个数字的丰度指数的简化形式是否相等（检查它们的分子和分母是否相等）来检查这两个数字是否为亲和数。

伪代码

procedure sumOfDivisors (n)
   ans = 1
   for i = 1 to sqrt(n)
      count = 0
      sum = 1
      term = 1
      while n % i == 0
         count = count + 1
         n = n / i
         term = term * i
         sum = sum + term
      ans = ans * sum
   if n >= 2
      ans = ans * (n + 1)
   end if
end procedure

procedure gcd (n1, n2)
   if n1 == 0
      return n2
   end if
   rem = n2 % n1
   return gcd (rem, n2)
end procedure

procedure friendlyPair (num1, num2)
   sum1 = sumOfDivisors (num1)
   sum2 = sumOfDivisors (num2)
   gcd1 = gcd (num1, sum1)
   gcd2 = gcd (num2, sum2)
   if (num1 / gcd1 == num2 / gcd2) && (sum1 / gcd1 == sum2 / gcd2)
      ans = TRUE
   else
      ans = FALSE
   end if
end procedure

示例：C++ 实现

在下面的程序中，我们通过比较分子和分母来检查两个数字的丰度指数的简化形式是否相同。

#include <bits/stdc++.h>
using namespace std;

// Function to find the sum of all the divisors of number n
int sumOfDivisors(int n){
   int ans = 1;
   
   // By looping till sqrt(n), we traverse all the prime factors of n
   for (int i = 2; i <= sqrt(n); i++){
      int cnt = 0, sum = 1, term = 1;
      while (n % i == 0){
         cnt++;
         
         // Reducing the value of n
         n /= i;
         term *= i;
         sum += term;
      }
      ans *= sum;
   }
   
   // When n is a prime number greater than 2
   if (n >= 2){
      ans *= (n + 1);
   }
   return ans;
}

// Function to find the gcd of two numbers
int gcd(int num1, int num2){
   if (num1 == 0) {
      return num2;
   }
   int rem = num2 % num1;
   return gcd(rem, num1);
}

// Function to find if two numbers are friendly pairs or not
int friendlyPair(int num1, int num2){

   // Finding the sum of all divisors of num1 and num2
   int sum1 = sumOfDivisors(num1);
   int sum2 = sumOfDivisors(num2);
   
   // Finding gcd of num and the sum of its divisors
   int gcd1 = gcd(num1, sum1);
   int gcd2 = gcd(num2, sum2);
   
   // Checking if the numerator and denominator of the reduced abundancy index are the same or not
   if (((num1 / gcd1) == (num2 / gcd2)) && ((sum1 / gcd1) == (sum2 / gcd2))){
      return true;
   }
   return false;
}
int main(){
   int num1 = 30, num2 = 140;
   cout << num1 << " and " << num2 << " are friendly pair : ";
   if (friendlyPair(num1, num2)){
      cout << "YES";
   }
   else{
      cout << "NO";
   }
   return 0;
}

输出

30 and 140 are friendly pair : YES

时间复杂度 − sumOfDivisors() 函数的时间复杂度为 O(n^1/2log₂n)。

空间复杂度 − O(1)

结论

总之，亲和数是丰度指数相同的两个自然数，即数字的所有约数之和与数字本身的比率。要查找两个数字是否为亲和数，请遵循上述方法，其中指定了时间复杂度为 O(n) 的暴力解决方案和时间复杂度为 O(n^1/2log₂n) 的优化解决方案。