logo

TechCodeview

Etsi yksilölliset parit siten, että jokainen elementti on pienempi tai yhtä suuri kuin N

Annettu kokonaisluku N etsi ja näytä parien määrä, joka täyttää seuraavat ehdot:

  • Näiden kahden luvun välisen etäisyyden neliö on yhtä suuri kuin LCM näistä kahdesta numerosta.
  • The GCD näistä kahdesta luvusta on yhtä suuri kuin kahden peräkkäisen kokonaisluvun tulo.
  • Parin molempien lukujen tulee olla pienempiä tai yhtä suuria kuin N.

HUOMAA: Vain ne parit tulisi näyttää, jotka noudattavat molempia yllä olevia ehtoja samanaikaisesti, ja näiden lukujen on oltava pienempiä tai yhtä suuria kuin N.

Esimerkkejä:   



  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)

Selitys:
Alla olevat taulukot antavat selkeän kuvan siitä, mitä löytyy:  

Etsi yksilölliset parit siten, että jokainen elementti on pienempi tai yhtä suuri kuin N' title=

muuntaa kaksinkertaiseksi javaksi

Yllä olevissa taulukoissa on GCD, joka on muodostettu kahden peräkkäisen luvun tulosta ja sitä vastaavista kerrannaisista, joissa kutakin arvoa vastaava ERIKOISPARI on olemassa. Vihreät merkinnät kullakin rivillä muodostavat yksilöllisen parin vastaavalle GCD:lle.
Huomautus: Yllä olevissa taulukoissa  

  1. Ensimmäiselle merkinnälle GCD=2 1. ja 2:n 2. kerrannainen muodostavat ainutlaatuisen parin (2 4)
  2. Vastaavasti 2. merkinnälle GCD=6 2. ja 6:n 3. kerrannainen muodostavat ainutlaatuisen parin (12 18)
  3. Samoin siirryttäessä Z:nnelle merkinnälle, eli GCD = Z*(Z+1), on selvää, että yksilöllinen pari käsittää Z:nnen ja (Z+1):nnen kerrannaisen GCD = Z*(Z+1). Nyt GCD:n Z:s kerrannainen on Z * (Z*(Z+1)) ja GCD:n (Z+1):s kerrannainen on (Z + 1) * (Z*(Z+1)).
  4. Ja koska raja on N, yksilöllisen parin toisen luvun on oltava pienempi tai yhtä suuri kuin N. Joten (Z + 1) * (Z*(Z+1))<= N. Simplifying it further the desired relation is derived Z3+ (2*Z2) + Z<=N

Tämä muodostaa kuvion ja matemaattisesta laskelmasta johdetaan, että tietylle N:lle tällaisten yksilöllisten parien kokonaismäärä (kuten Z) noudattaa alla esitettyä matemaattista suhdetta: 

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


Alla on vaadittu toteutus:  

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

Lähtö:   
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)

 

Aika monimutkaisuus : O(N1/3)
Aputila : O(1)