Solutions of GCD

Select solution language

bean Created at 3 likes

Nhận xét: Với mỗi số

$x$ bất kì, ta có tối đa

$log_2{(x)}$ lần thay đổi giá trị GCD Vậy, với mỗi vị trí

$i$ , ta có thể tìm xem lần thay đổi GCD tiếp theo nằm ở đâu, và nhảy nhanh đến đấy. Để xử lí việc này, ta có thể kết hợp cấu trúc dữ liệu Sparse Table và thuật toán tìm kiếm nhị phân. Với mỗi lần tìm kiếm này, ta mất

$\mathcal{O}{(log(n))}$ , do ta có thể dùng Sparse Table để tìm kiếm GCD của khoảng trong

$\mathcal{O}(1)$ , và tìm vị trí khiến cho GCD thay đổi trong

$log(n)$ Tổng độ phức tạp:

$\mathcal{O}{(n * log(n) * log(max(a)))} \approx 5 * 10^7$ Code tham khảo:

$cpp #include "bits/stdc++.h" using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } const int max_lg = 32 - __builtin_clz(n); vector<vector<int>> st(max_lg, vector<int>(n)); st[0] = a; for (int i = 1; i < max_lg; i++) { for (int j = 0; j < n; j++) { st[i][j] = __gcd(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } auto query = [&](int l, int r) { int lg = __lg(r - l + 1); return __gcd(st[lg][l], st[lg][r - (1 << lg) + 1]); }; auto nxt = [&](int i, int g) { int l = i, r = n; while (l < r) { int mid = (l + r) >> 1; int _g = query(i, mid); if (_g >= g) l = mid + 1; else r = mid; } return l; }; const int mod = int(1e9) + 7; int64_t res = 0; for (int i = 0; i < n; i++) { int g = a[i], lst = i; while (lst != n && g > 1) { int p = nxt(i, g); res += (int64_t(p - lst) * g) % mod; if (res >= mod) { res -= mod; } g = query(i, p); swap(p, lst); } res += (n - lst); } cout << res; }$