GCD operations CodeChef lunchtime Problem solution with explanation-
Problem Statement-
Consider a sequence , where initially, for each valid . You may perform any number of operations on this sequence (including zero). In one operation, you should choose two valid indices and , compute the greatest common divisor of and (let's denote it by ), and change both and to .
You are given a sequence . Is it possible to obtain this sequence, i.e. change to , using the given operations?
Input
- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains a single integer .
- The second line contains space-separated integers .
Output
For each test case, print a single line containing the string < class="mathjax-support" style="background: 0px 0px; border: none; box-sizing: border-box; color: #333333; font-family: Consolas, "Liberation Mono", Courier, monospace; line-height: 1.3; padding: 0px;">"YES"
"NO"
if it is impossible.Constraints
- for each valid
- the sum of over all test cases does not exceed
Subtasks
Subtask #1 (10 points):
Subtask #2 (20 points): there is at most one valid index such that
Subtask #3 (70 points): original constraints
Example Input
2
3
1 2 2
4
1 2 3 2
Example Output
NO
YES
Explanation
Example case 1: We cannot make the third element of the sequence become .
Example case 2: We can perform one operation with , which changes the sequence to .
problem link-https://www.codechef.com/LTIME88B/problems/GCDOPS
GCD operations codechef lunchtime Problem solution-
- GCD of two numbers (a,b) cannot grater then these two numbers.
array A has initially 1-N value.
Comments
Post a Comment