Bình luận

• 
  

  0

  

  deanqkhanh  đã bình luận lúc 18, Tháng 2, 2026, 6:10 ← sửa 2 →

  #pragma GCC optimize("Ofast")
  #pragma GCC optimize("unroll-loops")
  #pragma GCC optimize("inline")
  #include <iostream>
  #include <vector>
  #include <algorithm>
  #define gcd(a, b) __gcd(a, b)
  using namespace std;
  using ll = long long;
  int main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      // freopen("TASK.inp", "r", stdin);
      // freopen("TASK.out", "w", stdout);
      int n; cin >> n;
      vector<int> a(n);
      for (int &e : a) cin >> e;
      int len = -1, l = -1, r = -1;
      vector&lt;pair&lt;int, int>> cur, pre;
      for (int i = 0; i < n; ++i){
          cur.clear();
          cur.push_back({a[i], i});
          for (auto &p : pre){
              int ngcd = gcd(a[i], p.first);
              if (ngcd == cur.back().first) continue;
              else cur.push_back({ngcd, p.second});
          }
          if (cur.back().first == 1){
              // cerr << "cur.back().first == 1: " << cur.back().second + 1 << ' ' << i + 1 << endl
              if (len == -1 || i - cur.back().second + 1 < len){
                  len = i - cur.back().second + 1;
                  l = cur.back().second + 1;
                  r = i + 1;
              }
          }
          pre = cur;
      }
      if (len == -1){
          cout << -1;
      } else {
          cout << len << ' ' << l << ' ' << r;
      }
      return 0;
  }
  

• 
  

  -9

  

  buivietthanh  đã bình luận lúc 10, Tháng 7, 2023, 7:36

  top 1 VOI vua an cut

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -9

  

  buivietthanh  đã bình luận lúc 10, Tháng 7, 2023, 7:36

  toi an 2 cuc cut

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  4

  

  giabao8a70409042008  đã bình luận lúc 9, Tháng 7, 2023, 9:48

  Cho mình xin chia sẻ cách giải của mình ạ.

  Nhận xét:

  ~GCD(a[l], a[l+1], ..., a[r]) <= GCD(a[l], a[l+1], ..., a[r-1])~

  Chứng minh:

  Đặt ~d = GCD(a[l], a[l+1], ..., a[r-1])~ và ~D = GCD(a[l], a[l+1], ..., a[r])~

  Khi đó ~D = GCD(a[l], a[l+1], ..., a[r]) = GCD(GCD(a[l], a[l+1], ..., a[r - 1]), a[r]) = GCD(d, a[r])~

  Khi đó ~d~ chia hết cho ~D~.

  Mà ~d, D > 0~ (vì ~a[i] > 0~ ~(i = l, l+1, ..., r)~)

  Vậy ~d >= D~ hay ~GCD(a[l], a[l+1], ..., a[r-1]) >= GCD(a[l], a[l+1], ..., a[r])~

  Khi đó ta có phương pháp:

  Đầu tiên, ta duyệt ~l~ từ ~1~ -> ~n~. Sau đó, với mỗi l, ta chặt nhị phân để tìm ~r~ nhỏ nhất mà ~l <= r~ và ~GCD(a[l], a[l+1], ..., a[r]) = 1~

  Cách chặt nhị phân: (Dành cho những bạn chưa biết)

  Đặt ~lo = l + 1~, ~hi = n~

  Với mỗi lần, cho ~mid = (lo + hi) / 2~

  Nếu ~GCD(a[l], a[l+1], ..., a[mid]) = 1~ thì cập nhật ~r = mid~ và ~hi = mid - 1~, ngược lại thì cập nhật ~l = mid + 1~

  Lặp lại cho đến khi ~lo > hi~

  Sau đó cập nhật lại độ dài ngắn nhất, vị trí bắt đầu và kết thúc

  Tiếp theo, làm thế nào để tính ~GCD(a[l], a[l+1], ..., a[mid])~?

  Nếu chỉ có duyệt trâu thì tính ~GCD(a[l], a[l+1], ..., a[mid])~ có thể lên tới ~O(n*log(n))~

  Do có thêm phần chặt nhị phân nên độ phức tạp thời gian là ~O(n^2*log^2(n))~ => Sẽ bị TLE

  Do đó ta có 2 phương pháp: Sparse Table hoặc Segment Tree

  Sparse Table: Chi tiết

  Segment Tree: Chi tiết

  Phân tích về độ phức tạp thời gian:

  Sparse Table:

  Xây dựng: ~O(n*log^2(n))~

  Tính ~GCD(a[l], a[l+1], ..., a[mid])~: ~O(log(n))~

  Do có thêm phần chặt nhị phân nên: ~O(n*log^2(n))~

  => Tổng độ độ phức tạp thời gian là ~O(n*log^2(n))~ => AC

  Segment Tree:

  Xây dựng: ~O(n*log(n))~

  Tính ~GCD(a[l], a[l+1], ..., a[mid])~: ~O(log^2(n))~

  Do có thêm phần chặt nhị phân nên: ~O(n*log^3(n))~

  => Tổng độ độ phức tạp thời gian là ~O(n*log^3(n))~ => TLE

  Vậy để tính ~GCD(a[l], a[l+1], ..., a[mid])~ ta dùng Sparse Table.

  Code của mình để tham khảo (đã AC)

  Chúc các bạn một ngày vui vẻ! <3

• 
  

  0

  

  OrzSeaPosjtive  đã bình luận lúc 10, Tháng 7, 2023, 8:09

  2 pointer di ban