Editorial for Bedao Regular Contest 01 - GCDMAX


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nhận xét: Đề bài yêu cầu ta tìm ~GCD~ lớn nhất có thể của ~n-1~ phần tử còn lại khi bỏ một phần tử đi. Qua đó khi duyệt trâu bài toán, độ phức tạp lớn sẽ dấn đến TLE.

Độ phức tạp: : ~O(n^2 + n\log{\max a_i})~

Trước khi tối ưu hóa thời gian chạy, chúng ta cần biết một tính chất của ~GCD~: ~\gcd(a,\gcd(b,c))= \gcd(\gcd(a,b) ~~,c))~ và ~GCD~ càng duy trì trên đoạn ~[l,r]~ dài sẽ càng có xu hướng nhỏ đi.

Qua đó ta rút ra nhận xét: ~\gcd(a_1,a_2,…a_{i-1},a_{i+1}...,a_n)~ = ~\gcd(\gcd_{j=1}^{i - 1} a_j,~ ~ \gcd_{j=i + 1}^{n} a_j))~ (chú ý trường hợp n = 1)

Kết luận: Để tối ưu hóa thời gian chạy, ta tính ~GCD~ của tất cả ~prefix~ và ~suffix~. Nói cách khác, ~{prefix}_i = \gcd_{j=1}^{i} a_j~ và ~{suffix}_i = \gcd_{j=i}^{n} a_j~. Khi đó kết quả lớn nhất ta cần tìm là: ~\gcd({suffix}_{i-1},{prefix}_{i+1})~ ~,i \in [1,n]~.

Độ phức tạp: ~O(n\log{\max a_i})~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.