GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Friday 9 September 2022

[Solution] Good Pairs CodeChef Solution | Solution CodeChef



Problem

You are given an array A of length N.

A pair (i, j) (1\le i\lt j \le N) is said to be good if gcd(A_i, A_j) = lcm(A_i, A_j). Here gcd denotes the greatest common divisor and lcm denotes least common multiple.

Find the total number of good pairs present in the given array.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • The first line of each test case contains an integer N - the length of the array A.
  • The second line of each test case contains N space-separated integers A_1,A_2,\ldots,A_N.

Output Format

For each test case, output on a new line the total number of such good pairs possible in the given array.


Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

Explanation:

Test case 1: No good pair is present.

Test case 2: The good pairs (i, j) are: (2, 3), (3, 4), and (2, 4). To elaborate, gcd(A_2, A_3) = lcm(A_2, A_3) = 5.

Test case 3: The good pairs (i, j) are: (1, 4), (2, 3), (5, 6), (6, 7), and (5, 7). To elaborate, gcd(A_1, A_4) = lcm(A_1, A_4) = 2.

Test case 4: The good pair (i, j) are: (1, 2), and (3, 4). To elaborate, gcd(A_3, A_4) = lcm(A_3, A_4) = 18.

Test case 5: No good pair is present.

No comments:

Post a Comment