C++ 检查给定的两个数字是否是友好数对
友好数 - 根据数论,友好数是两个或更多具有相同盈余指数的数字。
盈余指数 - 自然数的盈余指数可以定义为自然数的所有除数之和与自然数本身的比率。
数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,使得\mathrm{\frac{\sigma(m)}{m}=\frac{\sigma(n)}{n}},则数n被称为“友好数”。
友好数对 - 具有相同盈余指数的两个数被称为“友好数对”。
问题陈述
给定两个数Num1和Num2。返回这两个数是否为友好数对。
示例
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}}
因为 \mathrm{\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}=\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
时间复杂度-O(n1/2log2n),针对sumOfDivisors()函数。
空间复杂度-O(1)
结论
总之,友好对是两个自然数,它们的富裕指数相同,即数字的所有除数的和与数字本身的比率。要确定两个数字是否为友好对,请按照上述方法指定时间复杂度为O(n)的蛮力解决方案以及时间复杂度为O(n1/2log2n)的优化解决方案。