Sequence GCD solution codechef

Sequence GCD solution codechef

 

SOLUTION:- CLICK HERE

 

You are given an integer sequence A=(A1,A2,,AN)A=(A1,A2,…,AN) of length NN and an integer MM such that 0M<i=1NAi0≤M<∑i=1NAi.

An integer sequence B=(B1,B2,,BN)B=(B1,B2,…,BN) of length NN is called good if:

  • 0BiAi0≤Bi≤Ai for each 1iN1≤i≤N
  • B1+B2++BN=MB1+B2+⋯+BN=M

Find the maximum value of gcd(A1B1,A2B2,,ANBN)gcd(A1−B1,A2−B2,…,AN−BN) over all good sequences BB. Here, gcdgcd denotes the greatest common divisor.

Note: gcd(a,b,c)=gcd(a,gcd(b,c))gcd(a,b,c)=gcd(a,gcd(b,c)) and gcd(a,0)=gcd(0,a)=agcd(a,0)=gcd(0,a)=a.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers N,MN,M.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the maximum value of gcd(A1B1,A2B2,,ANBN)gcd(A1−B1,A2−B2,…,AN−BN) over all good sequences BB.

Constraints

  • 1T101≤T≤10
  • 1N1051≤N≤105
  • 1Ai1051≤Ai≤105
  • 0M<i=1NAi0≤M<∑i=1NAi

Subtasks

Subtask #1 (50 points): 1N1041≤N≤104

Subtask #2 (50 points): Original constraints

Sample Input 1 

4
4 4
1 3 5 7
4 4
5 5 5 5
4 0
4 6 9 12
6 10
15 9 3 8 14 17

Sample Output 1 

3
4
1
7

Explanation

Test case 11: The optimal strategy is to take B=(1,0,2,1)B=(1,0,2,1). The answer is gcd(11,30,52,71)=gcd(0,3,3,6)=3gcd(1−1,3−0,5−2,7−1)=gcd(0,3,3,6)=3.

Test case 22: The optimal strategy is to take B=(1,1,1,1)B=(1,1,1,1). The answer is gcd(51,51,51,51)=gcd(4,4,4,4)=4gcd(5−1,5−1,5−1,5−1)=gcd(4,4,4,4)=4.

SOLUTION:- CLICK HERE

Leave a Comment

Your email address will not be published.