logo

TechCodeview

Raskite unikalias poras, kad kiekvienas elementas būtų mažesnis arba lygus N

Duotas sveikasis skaičius N, raskite ir parodykite porų, atitinkančių šias sąlygas, skaičių:

  • Atstumo tarp šių dviejų skaičių kvadratas yra lygus LCM iš tų dviejų skaičių.
  • The GCD tų dviejų skaičių yra lygus dviejų iš eilės einančių sveikųjų skaičių sandaugai.
  • Abu skaičiai poroje turi būti mažesni arba lygūs N.

PASTABA: Turi būti rodomos tik tos poros, kurios vienu metu atitinka abi pirmiau nurodytas sąlygas, o šie skaičiai turi būti mažesni arba lygūs N.

Pavyzdžiai:   



  Input:   10   Output:   No. of pairs = 1 Pair no. 1 --> (2 4)   Input:   500   Output:   No. of pairs = 7 Pair no. 1 --> (2 4) Pair no. 2 --> (12 18) Pair no. 3 --> (36 48) Pair no. 4 --> (80 100) Pair no. 5 --> (150 180) Pair no. 6 --> (252 294) Pair no. 7 --> (392 448)

Paaiškinimas:
Žemiau pateiktos lentelės aiškiai parodys, ką reikia rasti:  

Raskite unikalias poras, kad kiekvienas elementas būtų mažesnis arba lygus N' title=

rinkinys vs žemėlapis

Aukščiau pateiktose lentelėse parodytas GCD, sudarytas iš dviejų iš eilės einančių skaičių sandaugos ir atitinkamų jų kartotinių, kuriuose egzistuoja UNIKALI PORA, atitinkanti kiekvieną reikšmę. Žali įrašai kiekvienoje eilutėje sudaro unikalią atitinkamo GCD porą.
Pastaba: Aukščiau pateiktose lentelėse  

  1. Pirmajam įrašui GCD=2 1 ir 2 kartotinis sudaro unikalią porą (2 4)
  2. Panašiai 2 įrašui GCD=6 2 ir 3 kartotinis 6 sudaro unikalią porą (12 18)
  3. Panašiai pereinant prie Z-ojo įrašo, ty GCD = Z*(Z+1), aišku, kad unikalią porą sudarys Z ir (Z+1) kartotinis GCD = Z*(Z+1). Dabar Z-asis GCD kartotinis yra Z * (Z*(Z+1)), o (Z+1) GCD kartotinis bus (Z + 1) * (Z*(Z+1)).
  4. Ir kadangi riba yra N, todėl antrasis skaičius unikalioje poroje turi būti mažesnis arba lygus N. Taigi (Z + 1) * (Z*(Z+1))<= N. Simplifying it further the desired relation is derived Z3+ (2*Z2) + Z<=N

Tai sudaro modelį ir iš matematinio skaičiavimo išvesta, kad tam tikram N bendras tokių unikalių porų skaičius (tarkime Z) atitiks toliau pateiktą matematinį ryšį: 

Z3 + (2*Z2) + Z <= N


Žemiau pateikiamas reikalingas diegimas:  

C 
// C program for finding the required pairs #include  #include  // Finding the number of unique pairs int No_Of_Pairs(int N) {  int i = 1;  // Using the derived formula  while ((i * i * i) + (2 * i * i) + i <= N)  i++;  return (i - 1); } // Printing the unique pairs void print_pairs(int pairs) {  int i = 1 mul;  for (i = 1; i <= pairs; i++) {  mul = i * (i + 1);  printf('Pair no. %d --> (%d %d)n'  i (mul * i) mul * (i + 1));  } } // Driver program to test above functions int main() {  int N = 500 pairs mul i = 1;  pairs = No_Of_Pairs(N);  printf('No. of pairs = %d n' pairs);  print_pairs(pairs);  return 0; }
Java 
// Java program for finding // the required pairs import java.io.*; class GFG  {    // Finding the number  // of unique pairs  static int No_Of_Pairs(int N)  {  int i = 1;    // Using the derived formula  while ((i * i * i) +   (2 * i * i) + i <= N)  i++;    return (i - 1);  }    // Printing the unique pairs  static void print_pairs(int pairs)  {  int i = 1 mul;  for (i = 1; i <= pairs; i++)  {  mul = i * (i + 1);  System.out.println('Pair no. ' + i + ' --> (' +   (mul * i) + ' ' +   mul * (i + 1) + ')');   }  }    // Driver code  public static void main (String[] args)  {  int N = 500 pairs mul i = 1;  pairs = No_Of_Pairs(N);    System.out.println('No. of pairs = ' + pairs);  print_pairs(pairs);  } } // This code is contributed by Mahadev.
Python3 
# Python3 program for finding the required pairs # Finding the number of unique pairs def No_Of_Pairs(N): i = 1; # Using the derived formula while ((i * i * i) + (2 * i * i) + i <= N): i += 1; return (i - 1); # Printing the unique pairs def print_pairs(pairs): i = 1; mul = 0; for i in range(1 pairs + 1): mul = i * (i + 1); print('Pair no.'  i ' --> (' (mul * i) ' ' mul * (i + 1) ')'); # Driver Code N = 500; i = 1; pairs = No_Of_Pairs(N); print('No. of pairs = ' pairs); print_pairs(pairs); # This code is contributed # by mits
C# 
// C# program for finding // the required pairs using System; class GFG  {   // Finding the number // of unique pairs static int No_Of_Pairs(int N) {  int i = 1;  // Using the derived formula  while ((i * i * i) +   (2 * i * i) + i <= N)  i++;  return (i - 1); } // Printing the unique pairs static void print_pairs(int pairs) {  int i = 1 mul;  for (i = 1; i <= pairs; i++)  {  mul = i * (i + 1);  Console.WriteLine('Pair no. ' + i + ' --> (' +   (mul * i) + ' ' +   mul * (i + 1) + ')');   } } // Driver code static void Main() {  int N = 500 pairs;  pairs = No_Of_Pairs(N);  Console.WriteLine('No. of pairs = ' +   pairs);  print_pairs(pairs); } } // This code is contributed by mits
PHP 
 // PHP program for finding  // the required pairs // Finding the number  // of unique pairs function No_Of_Pairs($N) { $i = 1; // Using the  // derived formula while (($i * $i * $i) + (2 * $i * $i) + $i <= $N) $i++; return ($i - 1); } // Printing the unique pairs function print_pairs($pairs) { $i = 1; $mul; for ($i = 1; $i <= $pairs; $i++) { $mul = $i * ($i + 1); echo 'Pair no.'  $i ' --> ('  ($mul * $i) ' ' $mul * ($i + 1)') n'; } } // Driver Code $N = 500; $pairs; $mul; $i = 1; $pairs = No_Of_Pairs($N); echo 'No. of pairs = ' $pairs  ' n'; print_pairs($pairs); // This code is contributed // by Akanksha Rai(Abby_akku) ?>
JavaScript 
<script> // Javascript program for finding the  // required pairs // Finding the number of unique pairs function No_Of_Pairs(N) {  let i = 1;  // Using the derived formula  while ((i * i * i) +  (2 * i * i) + i <= N)  i++;  return (i - 1); } // Printing the unique pairs function print_pairs(pairs) {  let i = 1 mul;  for(i = 1; i <= pairs; i++)   {  mul = i * (i + 1);  document.write('Pair no. ' + i +   ' --> (' + (mul * i) +  ' ' + mul * (i + 1) +   ')  
');  } } // Driver code let N = 500 pairs mul i = 1; pairs = No_Of_Pairs(N); document.write('No. of pairs = ' +   pairs + '  
'); print_pairs(pairs); // This code is contributed by mohit kumar 29 </script>
C++14 
// C++ code for the above approach: #include    using namespace std; // Finding the number of unique pairs int No_Of_Pairs(int N) {  int i = 1;  // Using the derived formula  while ((i * i * i) + (2 * i * i) + i <= N)  i++;  return (i - 1); } // Printing the unique pairs void print_pairs(int pairs) {  int i = 1 mul;  for (i = 1; i <= pairs; i++) {  mul = i * (i + 1);  cout << 'Pair no. '<< i <<' --> (' << (mul * i) << ' '<< mul * (i + 1) << ')' <<endl;;  } } // Driver Code int main() {  int N = 500 pairs mul i = 1;  pairs = No_Of_Pairs(N);  cout << 'No. of pairs = ' << pairs << endl;  print_pairs(pairs);  return 0; }

Išvestis:   
No. of pairs = 7 Pair no. 1 --> (2 4) Pair no. 2 --> (12 18) Pair no. 3 --> (36 48) Pair no. 4 --> (80 100) Pair no. 5 --> (150 180) Pair no. 6 --> (252 294) Pair no. 7 --> (392 448)

 

Laiko sudėtingumas : O (N1/3)
Pagalbinė erdvė : O(1)