Editorial for Lớp học đặc biệt
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Lời giải
*Nhận xét 1: *Giá trị yêu thích chung lớn nhất của một nhóm chính là yêu cầu đi tìm ước chung lớn nhất của nhóm này.
Nhận xét 2: Với số lượng query ~m = 2 * 10^6~ thì phải trả lời query trong ~O(1)~. Để giải quyết vấn đề này ta có thuật toán Sparse Table.
Code tham khảo
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 100110;
int a[N], f[N][16], g[N], n;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
auto bit = [] (int i) {return 1 << i;};
g[1] = 0;
for (int i = 2; i < N; ++i) g[i] = log2(i);
for (int i = 0; i < n; ++i) f[i][0] = a[i];
for (int k = 1; bit(k) <= n; ++k) {
for (int i = 0; i + bit(k) <= n; ++i)
f[i][k] = __gcd(f[i][k - 1], f[i + bit(k - 1)][k - 1]);
}
auto get = [=] (int l, int r) {
int G = g[r - l + 1];
return __gcd(f[l][G], f[r - bit(G) + 1][G]);
};
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r;
--l, --r;
cout << get(l, r) << '\n';
}
return 0;
}
Comments