Page Contents
Codechef Sequence GCD WGCD Solution
You are given an integer sequence A=(A1,A2,…,AN)A=(A1,A2,…,AN) of length NN and an integer MM such that 0≤M<∑i=1NAi0≤M<∑i=1NAi.
An integer sequence B=(B1,B2,…,BN)B=(B1,B2,…,BN) of length NN is called good if:
- 0≤Bi≤Ai0≤Bi≤Ai for each 1≤i≤N1≤i≤N
- B1+B2+⋯+BN=MB1+B2+⋯+BN=M
Find the maximum value of gcd(A1−B1,A2−B2,…,AN−BN)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(A1−B1,A2−B2,…,AN−BN)gcd(A1−B1,A2−B2,…,AN−BN) over all good sequences BB.
Constraints
- 1≤T≤101≤T≤10
- 1≤N≤1051≤N≤105
- 1≤Ai≤1051≤Ai≤105
- 0≤M<∑i=1NAi0≤M<∑i=1NAi
Subtasks
Subtask #1 (50 points): 1≤N≤1041≤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(1−1,3−0,5−2,7−1)=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(5−1,5−1,5−1,5−1)=gcd(4,4,4,4)=4gcd(5−1,5−1,5−1,5−1)=gcd(4,4,4,4)=4.
SOLUTION WILL BE POST FROM NEXT DAY TILL THEN PLEASE WAIT….
February Long 2022 – II (Rated for Div 3)
- Area Sums in Convex Polygons PLYARSM Solution Codechef
- World Chess Championship WCC Solution Codechef
- Chef and NextGen HELIUM3 Solution Codechef
- Sequence GCD WGCD Solution Codechef
- Bitwise swaps BITSWAPS Solution Codechef
- Xor Palindrome XORPAL Solution Codechef
- Avoid Fixed Points NOFIX Solution Codechef