2
$\begingroup$

Can anyone please help me out with the https://www.codechef.com/JUNE19B/problems/SUMAGCD question?

Chef has a sequence of positive integers $A_1,A_2, \dots, A_N$. He wants to split this sequence into two non-empty (not necessarily contiguous) subsequences $B$ and $C$ such that $\text{GCD}(B) + \text{GCD}(C)$ is maximum possible. Help him find this maximum value.

Example case 1: For example, the sequence $A=(4,4,7,6)$ can be divided into subsequences $B=(4,4,6)$ and $C=(7)$.

But how the output comes out to be 9 As gcd of 7 is 1 itself.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is the question here to do with how the example case works? $\endgroup$
    – hexomino
    Jun 22 '19 at 20:22
  • 2
    $\begingroup$ In that case, GCD of a single integer is the integer itself, thus $GCD(7)=7$ ... $\endgroup$
    – athin
    Jun 22 '19 at 22:38
  • 1
    $\begingroup$ @athin has it right. Note that the definition of GCD given is "the largest positive integer that divides each element of this sequence," which does not necessarily imply the output is smaller than the inputs. $\endgroup$
    – RShields
    Jun 23 '19 at 14:44
2
$\begingroup$

Example case 1:** For example, the sequence $A=(4,4,7,6)$ can be divided into subsequences $B=(4,4,6)$ and $C=(7)$.

GCD(B) = 2
GCD(C) = 7
GCD(B) + GCD(C) = 2 + 7 = 9

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.