minhnhatmn16
commented
2 years ago TH1: Trong dãy có a[i]=1 Số phép toán ít nhất là n-d (với d là số lượng số 1 trong dãy) TH2: Không có số 1 Tìm đoạn con ngắn nhất [i..j] có ước chung lớn nhất là 1
- Nếu không có đoạn con như vậy thì in -1
- Nếu có thì in n-1 + len-1 (với len là độ dài dãy con ngắn nhất có gcd=1) len-1 : số bước để biến dãy [i,j] có 1 số thành 1 (vd: 4 6 3 thì gcd(4,6)=2 gcd(2,3)=1 vậy có 2 bước) n-1 : số bước để biến các số còn lại thành 1 (công thức ở TH1 với d=1 )
Thao tác trên dãy số - Luyện Code Online
https://luyencode.net/problem/COSEQ