Comments

• 
  

  -8

  

  buivietthanh  commented on July 10, 2023, 7:36 a.m.

  top 1 VOI vua an cut

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  -8

  

  buivietthanh  commented on July 10, 2023, 7:36 a.m.

  toi an 2 cuc cut

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  2

  

  giabao8a70409042008  commented on July 9, 2023, 9:48 a.m.

  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  commented on July 10, 2023, 8:09 a.m.

  2 pointer di ban