Editorial for GCD

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: Yunan

Nguồn: AtCoder

Về hướng giải, ta sẽ nhanh chóng tính giá trị lớn nhất của ước chung lớn nhất $M_i$ ~M_i~ khi thay đổi $A_i$ ~A_i~, với mọi $i$ ~i~, sau đó in ra giá trị lớn nhất trong các $M_i$ ~M_i~.

Trước hết, nếu quyết định thay đổi $A_i$ ~A_i~, ta có thể thay nó bằng $\text{GCD}$ ~\text{GCD}~ của $N - 1$ ~N - 1~ số còn lại. Khi đó, phép toán "thay đổi số nguyên $A_i$ ~A_i~" tương đương với việc "xóa số nguyên $A_i$ ~A_i~".

Ngoài ra, ký hiệu $\text{GCD}$ ~\text{GCD}~ của hai số nguyên $X$ ~X~ và $Y$ ~Y~ là $gcd(X, Y)$ ~gcd(X, Y)~. Phép toán $\text{GCD}$ ~\text{GCD}~ có tính kết hợp, tức là với mọi số nguyên $X, Y, Z$ ~X, Y, Z~: $gcd(gcd(X,Y),Z)=gcd(X,gcd(Y,Z))$ ~gcd(gcd(X,Y),Z)=gcd(X,gcd(Y,Z))~. Nói đơn giản, $\text{GCD}$ ~\text{GCD}~ có tính chất "tính từ vị trí nào trước cũng cho cùng một kết quả". Khi đó, ta có thể sử dụng kỹ thuật sau: Với $i = 1, 2, ..., N + 1$ ~i = 1, 2, ..., N + 1~, định nghĩa $L(i)$ ~L(i)~ và $R(i)$ ~R(i)~ như sau:

\[L(i)=gcd(A_1,A_2,...,A_i)\] \[R(i)=gcd(A_i,A_{i+1},...,A_N)\]

Để thuận tiện, ta quy ước $L(0)=R(N+1)=0$ ~L(0)=R(N+1)=0~ và với mọi số nguyên $X$ ~X~: $gcd(0,X)=gcd(X,0)=X$ ~gcd(0,X)=gcd(X,0)=X~. Khi quyết định thay đổi $A_i$ ~A_i~ (tức là xóa $A_i$ ~A_i~), $\text{GCD}$ ~\text{GCD}~ của $N-1$ ~N-1~ số còn lại là: $M_i=gcd(L(i-1),R(i+1))$. Việc tính toán các $L(i)$ ~L(i)~ và $R(i)$ ~R(i)~ có tư tưởng tương tự như Tổng tiền tố (Prefix Sum).

Như vậy, sau khi tính được $M_1,M_2,...,M_N$ thì đáp án chính là $\max(M_1,M_2,...,M_N)$.

Độ phức tạp: $O(N.log(A_1)+ N.log(A_N))$

Editorial for GCD

Comments