Ta sẽ sử dụng tìm kiếm nhị phân để giải quyết bài này, cụ thể như sau:

• Nhận xét đầu tiên là chúng ta không thể tăng tất cả \(a_i\) về cùng một giá trị \(d\), mà cần phải chọn giá trị \(d\) sao cho nó là ước chung lớn nhất của \(a_1, a_2, \ldots, a_n\). Theo Euclid, ta có:

  • \(gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(gcd(a,c),b) = gcd(gcd(b,c),a)\). Chú ý rằng ta chỉ cần áp dụng công thức này trên hai phần tử một lần, và sau đó tiếp tục áp dụng lên phần tử tiếp theo.

• Nhận xét thứ hai là với một giá trị \(d\), ta có thể tìm được số lần cộng cần thiết sao cho \(a_1, a_2, \ldots, a_n\) đều chia hết cho \(d\). Nếu các số đều chia hết cho \(d\), thì chúng ta có thể chia tất cả các số cho \(d\) mà không ảnh hưởng tới giá trị \(\gcd(a_1, a_2, \ldots, a_n)\), và vì thế giá trị \(d\) sẽ là ước chung lớn nhất của các số đã được chia hết cho \(d\).

• Nhận xét thứ ba là nếu các số đã được chia hết cho \(d\), thì các giá trị \(a_i\) cần được tăng lên ít nhất \(x - a_i \bmod x\) để đảm bảo rằng chúng đều chia hết cho \(x\). Lưu ý rằng ta không cần phải tăng tất cả các giá trị lên đến \(x\), vì nếu các giá trị đã đều chia hết cho \(x\) thì chúng ta có thể chia tất cả các số cho \(x\) mà không ảnh hưởng tới giá trị \(\gcd(a_1, a_2, \ldots, a_n)\).

Với ba nhận xét trên, ta có thể sử dụng tìm kiếm nhị phân để tìm giá trị \(d\) lớn nhất có thể. Đối với mỗi giá trị \(d\), ta cần tính toán chi phí cần thiết để chuyển từ \(a_i\) thành \(a_i'\) sao cho \(d\) là ước chung lớn nhất của \(a_1',a_2',\ldots,a_n'\).

Để tính chi phí này, ta cần biết số lần cần chọn \(i\) và cộng \(1\) vào \(a_i\) để chuyển từ \(a_i\) thành \(a_i'\), đồng thời tính tổng của \(a_i'\) trong quá trình chuyển đổi.

Ta có thể tính chi phí này cho mỗi \(d\) bằng cách duyệt qua các phần tử \(a_i\) và đếm số lần phải cộng thêm vào \(a_i\) để \(a_i\) chia hết cho \(d\). Để tính tổng, ta sử dụng mảng tích lũy. Để cụ thể hơn, định nghĩa \(cnt_x\) là số lần xuất hiện của \(x\) trong dãy \(a\), \(sum_x\) là tổng của các phần tử \(a_i\) có giá trị là \(x\). Ta tính mảng tích lũy cho \(cnt\) và \(sum\) theo công thức sau:

• \(cnt_c[i] = \sum_{j = 1}^{i} cnt_j\)
• \(sum_c[i] = \sum_{j = 1}^{i} sum_j\)

Với \(d\) cho trước, ta sử dụng hai mảng tích lũy \(cnt_c\) và \(sum_c\) để tính chi phí chuyển từ \(a\) thành \(a'\). Trong quá trình duyệt, ta duyệt qua các khoảng \([l, r]\) có độ dài là \(d\) để tính số phần tử cần chuyển đổi và tổng giá trị của chúng. Cuối cùng, chi phí cần thiết để chuyển từ \(a\) thành \(a'\) cho giá trị \(d\) cho trước là \(rd - s\), với \(r\) là số lần \(d\) xuất hiện trong dãy \(a\), \(s\) là tổng giá trị của các phần tử \(a_i\) có giá trị là \(d\). Để tính \(r\) và \(s\), ta sử dụng mảng tích lũy \(cnt_c\) và \(sum_c\) như sau:

• \(r = cnt_c[min(r,MAX)] - cnt_c[l]\)
• \(s = sum_c[min(r,MAX)] - sum_c[l]\)

Trong đó, \(MAX\) là giá trị lớn nhất có thể của một phần tử trong dãy \(a\). Do đó, ta cần duyệt qua các giá trị \(d\) từ \(2\) đến \(MAX\) và tìm giá trị \(d\) lớn nhất thỏa mãn chi phí không vượt quá \(k\). Nếu không tìm được giá trị \(d\) thỏa mãn ta sẽ trả về \(-1\) để thể hiện không tìm được kết quả.

Để tìm giá trị \(d\) lớn nhất thỏa mãn chi phí không vượt quá \(k\), ta có thể sử dụng tìm kiếm nhị phân. Ta sẽ tìm giá trị lớn nhất của \(d\) sao cho tổng chi phí của việc thay đổi các phần tử trong dãy \(a\) sao cho mỗi phần tử đều chênh lệch không quá \(d\) so với các phần tử khác là không vượt quá \(k\).

Cụ thể, ta sẽ duyệt qua các giá trị \(d\) từ \(2\) đến \(MAX\), và đối với mỗi giá trị \(d\), ta sử dụng tìm kiếm nhị phân để tìm giá trị \(x\) lớn nhất thỏa mãn tổng chi phí không vượt quá \(k\). Trong quá trình tìm kiếm nhị phân, ta sẽ tính tổng chi phí cho giá trị \(x\) hiện tại, và so sánh với giá trị \(k\) để quyết định cần tăng hay giảm giá trị \(x\) tiếp theo.

Khi tìm được giá trị \(d\) lớn nhất thỏa mãn chi phí không vượt quá \(k\), ta sẽ trả về giá trị đó. Nếu không tìm được giá trị \(d\) thỏa mãn ta sẽ trả về \(-1\).

Độ phức tạp thời gian của thuật toán là \(O(MAX \times \log(n) \times \log(k))\).