logo

TechCodeview

Atrodiet unikālus pārus, lai katrs elements būtu mazāks vai vienāds ar N

Dots vesels skaitlis N, atrodiet un parādiet pāru skaitu, kas atbilst šādiem nosacījumiem:

  • Attāluma kvadrāts starp šiem diviem skaitļiem ir vienāds ar LCM no šiem diviem skaitļiem.
  • The GCD no šiem diviem skaitļiem ir vienāds ar divu secīgu veselu skaitļu reizinājumu.
  • Abiem skaitļiem pārī jābūt mazākiem vai vienādiem ar N.

PIEZĪME: Jāattēlo tikai tie pāri, kas vienlaikus atbilst abiem iepriekš minētajiem nosacījumiem, un šiem skaitļiem ir jābūt mazākiem vai vienādiem ar N.

Piemēri:   



  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)

Paskaidrojums:
Tālāk redzamās tabulas sniegs skaidru priekšstatu par to, kas ir atrodams:  

Atrodiet unikālus pārus, lai katrs elements būtu mazāks vai vienāds ar N' title=

dziedināt rīks gimp

Augšējās tabulās ir parādīts GCD, ko veido divu secīgu skaitļu un to atbilstošo reizinājumu reizinājums, kurā katrai vērtībai atbilst UNIKĀLS PĀRIS. Zaļie ieraksti katrā rindā veido unikālu pāri attiecīgajam GCD.
Piezīme: Iepriekš minētajās tabulās  

  1. Pirmajam ierakstam GCD=2 1. un 2. reizinieks veido unikālo pāri (2 4)
  2. Līdzīgi 2. ierakstam GCD=6 2. un 3. daudzkārtnis 6 veido unikālo pāri (12 18)
  3. Līdzīgi pārejot uz Z. ierakstu, t.i., GCD = Z*(Z+1), ir skaidrs, ka unikālais pāris sastāvēs no GCD = Z*(Z+1) Z. un (Z+1) daudzkārtņa. Tagad GCD Z daudzkārtnis ir Z * (Z*(Z+1)) un (Z+1) GCD daudzkārtnis būs (Z + 1) * (Z*(Z+1)).
  4. Tā kā ierobežojums ir N, otrajam skaitlim unikālajā pārī ir jābūt mazākam vai vienādam ar N. Tātad (Z + 1) * (Z*(Z+1))<= N. Simplifying it further the desired relation is derived Z3+ (2*Z2) + Z<=N

Tas veido modeli, un no matemātiskā aprēķina tiek iegūts, ka dotajam N šādu unikālo pāru kopējais skaits (piemēram, Z) sekos matemātiskajai sakarībai, kas parādīta zemāk: 

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


Tālāk ir norādīta nepieciešamā ieviešana:  

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

Izvade:   
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)

 

Laika sarežģītība : O(N1/3)
Palīgtelpa : O(1)