Soluție HackerRank pentru John and GCD list, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: John and GCD list
- Domeniu: Number Theory
- Limbaj: C++14
Challenge: John and GCD list
Subdomeniu: Number Theory (number-theory)
Scor cont: 50.0 / 50
Submission status: Accepted
Submission score: 1.0
Submission ID: 464734630
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/john-and-gcd-list/problem
Cerință
John is new to Mathematics and does not know how to calculate [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) of numbers. So he wants you to help him in a few GCD calculations. John has a list A of numbers, indexed _1_ to N. He wants to create another list B having _N+1_ numbers, indexed from _1_ to _N+1_, and having the following property:
GCD(B[i], B[i+1]) = A[i], ∀ 1 ≤ i ≤ N
As there can be many such lists, John wants to know the list B in which sum of all elements is minimum. It is guaranteed that such a list will always exist.
Input Format
The first line contains an integer T, i.e., the number of the test cases. T testcases follow.
The first line of each test case contains an integer N, i.e., the number of elements in the array.
The second line of each test case contains N space separated integers that denote the elements of the list A.
Output Format
For each test case, print in a new line the list B such that each element is separated by a single space.
Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 10<sup>3</sup>
1 ≤ _A[i]_ ≤ 10<sup>4</sup>
1 ≤ _B[i]_
Sample Input
2
3
1 2 3
3
5 10 5
Sample Output
1 2 6 3
5 10 10 5
Explanation
For the first testcase,
GCD(1,2) = 1
GCD(2,6) = 2
GCD(6,3) = 3
sum = 1+2+6+3 = 12 which is minimum among all possible list B
For the second testcase,
GCD(5, 10) = 5
GCD(10, 10) = 10
GCD(10, 5) = 5
sum = 5 + 10 + 10 + 5 = 30 which is the minimum among all possible list B
Cod sursă
//john-and-gcd-list.cpp
//John and GCD list
//Weekly Challenges - Week 8
//Author: derekhh
#include<iostream>
using namespace std;
int a[1000];
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
cout << a[0] << " ";
for (int i = 1; i < n; i++)
cout << lcm(a[i - 1], a[i]) << " ";
cout << a[n - 1] << endl;
}
return 0;
}