檢查給定的兩個數字是否是友善數對-C++-PHP中文網

首頁

後端開發

C++

檢查給定的兩個數字是否是友善數對

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Aug 26, 2023 pm 11:41 PM

友善數對

檢查給定的兩個數字是否是友善數對

友善數 − 根據數論，友善數是指兩個或更多具有相同豐度指數的數。

豐富度指數 - 自然數的豐富度指數可以定義為自然數的所有除數總和與自然數本身之間的比率。

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