Hướng dẫn giải của Tối giản
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Trước hết, ta cần nhận xét 1 tính chất quan trọng của ~x~: ~x~ phải là phần tử có giá trị nhỏ nhất trong đoạn "có thể tối giản".
Một hướng đi có thể nghĩ đến trong bài này là với mỗi ~a_i~, nó sẽ đóng vai trò là phần tử ~x~ trong bao nhiêu đoạn con. ~a_i~ phải là phần tử nhỏ nhất và duy nhất (1), đồng thời mọi phần tử trong đoạn phải chia hết cho ~a_i~, hay ~UCLN~ của đoạn bằng ~a_i~ (2).
Với (1), ta có thể sử dụng stack đơn điệu để tìm khoảng ~[L, R]~ thỏa mãn ~a_i~ nhỏ nhất và duy nhất.
Với (2), sau khi tìm được đoạn ~[L, R]~ thỏa mãn (1), ta cần thu hẹp lại đoạn thành ~[L', R']~ ~(L \le L', R \ge R')~ để ~gcd(a_L, a_{L+1}, ..., a_R') = a_i~. Ở bước này, ta có thể sử dụng chặt nhị phân 2 lần để tìm ~L'~ và ~R'~. Với mỗi lần sử dụng hàm ~check~ trong chặt nhị phân, ta cần biết được ~gcd(a_{mid}, a_{mid+1}, ..., a_i)~ hoặc ~gcd(a_i, a_{i+1}, ..., a_{mid})~ là bao nhiêu. Bước này có thể sử dụng Segment Tree, tuy nhiên với độ phức tạp ~O((logn)^2)~ với mỗi lần truy vấn, độ phức tạp cuối cùng lên tới ~O(n(logn)^3)~ có thể bị TLE. Để khắc phục, ta cần cải tiến sử dụng ~Sparse~ ~Table~ với độ phức tạp mỗi truy vấn chỉ là ~O(logn)~, với tổng độ phức tạp ~O(n(logn)^2)~
Code mẫu
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
using namespace std;
const int MAXN = 3e5 + 5;
const int LOG = 17;
int n, a[MAXN], l[MAXN], r[MAXN];
int gcd[MAXN][LOG + 2];
void prep() {
stack<int> L, R;
for (int i = 1; i <= n; i++) {
while (L.size() && a[L.top()] > a[i]) L.pop();
l[i] = L.size() ? L.top() + 1 : 1;
L.push(i);
}
for (int i = n; i >= 1; i--) {
while (R.size() && a[R.top()] > a[i]) R.pop();
r[i] = R.size() ? R.top() - 1 : n;
R.push(i);
}
}
void buildRMQ() {
for (int i = 1; i <= n; i++) gcd[i][0] = a[i];
for (int k = 1; (1 << k) <= n; k++) {
for (int i = 1; i + (1 << k) <= n + 1; i++) {
gcd[i][k] = __gcd(gcd[i][k - 1], gcd[i + (1 << (k - 1))][k - 1]);
}
}
}
int getGCD(int l, int r) {
int log = log2(r - l + 1);
return __gcd(gcd[l][log], gcd[r - (1 << log) + 1][log]);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
prep();
buildRMQ();
int ans = 0;
for (int i = 1; i <= n; i++) {
int fl = i, fr = i;
int le = l[i], ri = i;
while (le <= ri) {
int mid = (le + ri) >> 1;
if (getGCD(mid, i) == a[i]) fl = mid, ri = mid - 1;
else le = mid + 1;
}
le = i, ri = r[i];
while (le <= ri) {
int mid = (le + ri) >> 1;
if (getGCD(i, mid) == a[i]) fr = mid, le = mid + 1;
else ri = mid - 1;
}
ans += (fr - i + 1) * (i - fl + 1) - 1;
}
cout << ans;
}
Bình luận
Cho em hỏi tại sao x lại phải là phần tử nhỏ nhất trong dãy vậy ạ
Xét 2 số ~a~ và ~b~. Nếu như ~a~ chia hết cho ~b~ thì có thể suy ra được rằng ~b \le a~. Do đó nếu như ta muốn tìm số ~x~ mà mọi số trong đoạn con chia hết cho nó, ~x~ cần phải không quá tất cả các số trong đoạn con, tương đương với ~x~ phải là số bé nhất.