각 요소가 N보다 작거나 같은 고유한 쌍을 찾습니다.

정수 N이 주어지면 다음 조건을 만족하는 쌍의 수를 찾아 표시하십시오.

두 숫자 사이의 거리의 제곱은 LCM 그 두 숫자 중.
그만큼 GCD 이 두 숫자의 곱은 연속된 두 정수의 곱과 같습니다.
쌍의 두 숫자는 모두 N보다 작거나 같아야 합니다.

메모: 위의 두 조건을 동시에 따르는 쌍만 표시되어야 하며 해당 숫자는 N보다 작거나 같아야 합니다.

예:

  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)

설명:
아래에 표시된 표는 무엇을 찾을 수 있는지 명확하게 보여줍니다.

각 요소가 N보다 작거나 같은 고유한 쌍을 찾습니다.' title=

안드로이드의 사과 이모티콘

위의 표는 두 개의 연속된 숫자와 각 값에 해당하는 UNIQUE PAIR가 존재하는 해당 배수의 곱으로 구성된 GCD를 보여줍니다. 각 행의 녹색 항목은 해당 GCD에 대한 고유한 쌍을 형성합니다.
메모: 위의 표에서

첫 번째 항목 GCD=2의 경우 첫 번째와 두 번째 2의 배수는 고유 쌍(2 4)을 형성합니다.
마찬가지로 두 번째 항목 GCD=6의 경우 두 번째와 세 번째 6의 배수는 고유 쌍(12 18)을 형성합니다.
마찬가지로 Z번째 항목, 즉 GCD = Z*(Z+1)에 대해 이동하면 고유한 쌍이 GCD = Z*(Z+1)의 Z번째 배수와 (Z+1)번째 배수로 구성된다는 것이 분명합니다. 이제 GCD의 Z번째 배수는 Z * (Z*(Z+1))이고 (Z+1)번째 GCD의 배수는 (Z + 1) * (Z*(Z+1))입니다.
그리고 한계는 N이므로 고유 쌍의 두 번째 숫자는 N보다 작거나 같아야 합니다. 따라서 (Z + 1) * (Z*(Z+1))<= N. Simplifying it further the desired relation is derived Z³+ (2*Z²) + Z<=N

이는 패턴을 형성하고 수학적 계산을 통해 주어진 N에 대해 이러한 고유 쌍(예: Z)의 총 수는 아래에 표시된 수학적 관계를 따를 것이라는 것이 도출됩니다.

Z³ + (2*Z²) + Z <= N

다음은 필수 구현입니다.

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

산출:

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)

시간 복잡도 : 에^1/3)
보조 공간 : ㅇ(1)