각 요소가 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)
설명:
아래에 표시된 표는 무엇을 찾을 수 있는지 명확하게 보여줍니다.
위의 표는 두 개의 연속된 숫자와 각 값에 해당하는 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 3 + (2*Z 2 ) + Z <=N
이는 패턴을 형성하고 수학적 계산을 통해 주어진 N에 대해 이러한 고유 쌍(예: Z)의 총 수는 아래에 표시된 수학적 관계를 따를 것이라는 것이 도출됩니다.
Z 3 + (2*Z 2 ) + 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# // 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)
