ابحث عن أزواج فريدة بحيث يكون كل عنصر أقل من أو يساوي N
بالنظر إلى عدد صحيح N، ابحث عن عدد الأزواج التي تستوفي الشروط التالية وأظهرها:
- مربع المسافة بين هذين الرقمين يساوي إل سي إم من هذين الرقمين.
- ال جي سي دي من هذين الرقمين يساوي منتج عددين صحيحين متتاليين.
- يجب أن يكون كلا الرقمين في الزوج أقل من أو يساوي 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)
توضيح:
الجداول المبينة أدناه سوف تعطي فكرة واضحة عما يمكن العثور عليه:
توضح الجداول أعلاه GCD المكونة من ناتج رقمين متتاليين ومضاعفاتها المقابلة والتي يوجد فيها زوج فريد يتوافق مع كل قيمة. تشكل الإدخالات الخضراء في كل صف زوجًا فريدًا لـ GCD المطابق.
ملحوظة: في الجداول أعلاه
- بالنسبة للإدخال الأول GCD=2، يشكل المضاعف الأول والثاني للرقم 2 الزوج الفريد (2 4)
- وبالمثل بالنسبة للإدخال الثاني GCD=6، يشكل المضاعف الثاني والثالث للرقم 6 الزوج الفريد (12 18)
- وبالمثل، ننتقل إلى إدخال Zth، أي بالنسبة إلى GCD = Z*(Z+1) فمن الواضح أن الزوج الفريد سيتألف من Zth و(Z+1) مضاعف GCD = Z*(Z+1). الآن المضاعف Z لـ GCD هو 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*ز 2 ) + ز <=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)
