检查给定的两个数字是否是友好数对

WBOY 转载: 2023-08-26 23:41:20 790浏览

检查给定的两个数字是否是友好数对

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

丰富度指数 - 自然数的丰富度指数可以定义为自然数的所有除数之和与自然数本身之间的比率。

数字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 mn，那么数n被称为“友好数”。

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

友好对 − 具有相同盈余指数的两个数字被称为“友好对”。

问题陈述

给定两个数字 Num1 和 Num2。如果这两个数字不是友好的一对，则返回。

示例 1

Input: Num1 = 30, Num2 = 140

Output: Yes

Explanation

的中文翻译为：

解释

$$\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

Explanation

的中文翻译为：

解释

$$\mathrm{\frac{\sigma(5)}{5}=\frac{1+5}{5}=\frac{6}{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不是友好的对。 p>

方法一：蛮力方法

解决这个问题的蛮力方法是先找到两个数字的所有约数的和，然后计算它们的丰度指数的值，并进行比较以得到结果。

伪代码

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;
}