GCDARR - Mảng GCD
Xem dạng PDF
Cho một mảng ~A~ gồm ~n~ phần tử, đánh số từ ~1..n~. Một mảng con ~(l, r) với (l ≤ r)~ của mảng ~A~ được gọi mảng GCD nếu GCD~(A_l, A_{l+1}, A_{l+2}, ..., A_r) = 1~.
Tìm mảng con ~(l, r)~ của ~A~ sao cho mảng con ~(l, r)~ là một mảng GCD và có độ dài ngắn nhất.
Lưu ý: GCD~(x_1, x_2, ..x_k)~ là ước số chung lớn nhất của các số ~x_1, x_2, ...x_k~. Ước số chung lớn nhất của các số ~x_1, x_2, ...x_k~ là một số nguyên dương ~X~ sao cho ~X~ lớn nhất và ~x_1, x_2, ...x_k~ đều chia hết cho ~X~.
Input
Dữ liệu đầu vào bao gồm:
- Dòng đầu tiên chứa một số nguyên dương ~n~ là số phần tử của mảng ~A (2 ≤ n ≤ 10^5)~.
- ~n~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên dương ~A_i (2 ≤ A_i ≤ 10^5)~.
Output
Đầu ra gồm một dòng chứa 3 số nguyên ~N, l, r~ lần lượt là độ dài ngắn nhất của mảng con của ~A~ là mảng GCD, vị trí bắt đầu và kết thúc của mảng con đó. Nếu có nhiều mảng con GCD có độ dài ngắn nhất, tìm mảng con có vị trí bắt đầu là nhỏ nhất. Nếu không tìm được mảng con nào của A là mảng GCD, xuất ra ~-1~.
Sample
Input #1
5
2
6
12
3
6
Output #1
4 1 4
Input #2
5
2
4
6
8
14
Output #2
-1
Problem source: Kc97ble - Free Contest 125
Bình luận
Ý tưởng của mình là : dùng 2 vòng for (dễ hiểu nhưng bị TLE) : tạo 3 thằng kết quả : minLen=n+1,left=n,right=n;
for(int l=0;l<n;i++){ tạo thằng current=a[i] => để lưu ước chung lớn nhất trong các đoạn từ l->r for(int r=l+1;r<n;r++){ current=gcd(current,a[j]); -NNếu current=1 , được lenTemp=r-l+1 thì kiểm tra thỏa mãn 1 trong 2 điều kiện: (lenTemp<minlen)hoặc(temp=min và i<left )=> cập nhật left=i ,right=j,minLen=lenTemp; rồi break luôn vì không cần xét đoạn đến r đằng sau nữa } }