資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查給定的兩個數字是否為親和數
親和數 − 根據數論，親和數是具有相同丰度指數的兩個或多個數。
丰度指數 − 自然數的丰度指數可以定義為自然數的所有約數之和與自然數本身的比率。
數字 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(n1/2log₂n)。
空間複雜度 − O(1)
結論
總之，親和數是丰度指數相同的兩個自然數，即數字的所有約數之和與數字本身的比率。要查詢兩個數字是否為親和數，請遵循上述方法，其中指定了時間複雜度為 O(n) 的暴力解決方案和時間複雜度為 O(n1/2log₂n) 的最佳化解決方案。
737 次瀏覽
