Menyemak sama ada dua nombor yang diberikan adalah pasangan mesra

Nombor Mesra − Mengikut teori nombor, nombor mesra ialah dua atau lebih nombor dengan indeks kelimpahan yang sama.

Indeks Kekayaan - Indeks kekayaan nombor asli boleh ditakrifkan sebagai nisbah antara jumlah semua pembahagi nombor asli dan nombor asli itu sendiri.

Kelimpahan nombor n boleh dinyatakan sebagai $mathrm{frac{sigma(n)}{n}}$, dengan $mathrm{sigma(n)}$ mewakili fungsi pembahagi yang sama dengan semua pembahagi n.

Sebagai contoh, indeks kelimpahan nombor asli 30 ialah,

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

Jika ada nombor m mn, maka nombor n itu dipanggil "nombor mesra".

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

Pasangan Mesra − Dua nombor dengan indeks lebihan yang sama dipanggil "pasangan mesra".

Pernyataan Masalah

Diberi dua nombor Num1 dan Num2. Mengembalikan jika dua nombor bukan pasangan yang mesra.

Contoh 1

Input: Num1 = 30, Num2 = 140

Output: Yes

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

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

Memandangkan, frac{sigma(30)}{30}=frac{sigma(140)}{140}, 30 dan 140 ialah pasangan nombor mesra.

Contoh contoh 2

Input: Num1 = 5, Num2 = 24

Output: No

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

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

Memandangkan $mathrm{frac{sigma(5)}{5}neqfrac{sigma(24)}{24}}$, 5 dan 24 bukan pasangan mesra.

Kaedah 1: Kaedah brute force

Cara brute force untuk menyelesaikan masalah ini adalah dengan terlebih dahulu mencari jumlah semua pembahagi dua nombor, kemudian mengira nilai indeks kelimpahannya, dan bandingkan untuk mendapatkan hasilnya.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, jumlah semua pembahagi dikira untuk mencari indeks kelimpahan.

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

Output

30 and 140 are friendly pair : YES

Kerumitan masa - O(n) kerana fungsi sumOfDivisors() merentasi gelung

Kerumitan ruang - O(1)

Kaedah 2: Mengurangkan bentuk indeks kelimpahan

Bentuk ringkas indeks kekayaan boleh didapati dengan membahagikan kedua-dua pengangka dan penyebut dengan pembahagi sepunya terbesar. Kami kemudian menyemak sama ada kedua-dua nombor itu adalah pasangan mesra dengan menyemak sama ada bentuk kekayaan yang dikurangkan adalah sama, iaitu menyemak sama ada pengangka dan penyebutnya adalah sama.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, kami menyemak sama ada indeks kelimpahan bentuk terkurang dua nombor adalah sama dengan membandingkan pengangka dan penyebut.

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

Output

30 and 140 are friendly pair : YES

Kerumitan masa - Kerumitan masa bagi fungsi sumOfDivisors() ialah O(n^1/2log2n).

Kerumitan ruang - O(1)

Kesimpulan

Ringkasnya, pasangan mesra merujuk kepada dua nombor asli dengan indeks kelimpahan yang sama, iaitu nisbah hasil tambah semua pembahagi nombor kepada nombor itu sendiri. Untuk mengetahui sama ada dua nombor ialah pasangan mesra, ikut pendekatan di atas, nyatakan penyelesaian brute-force dengan kerumitan masa O(n) dan penyelesaian yang dioptimumkan dengan kerumitan masa O(n^1/2log2n).

Atas ialah kandungan terperinci Menyemak sama ada dua nombor yang diberikan adalah pasangan mesra. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!