Cặp Ước Đẹp
Đề bài
Một cặp số $(x, y)$ được gọi là cặp ước đẹp nếu ước chung lớn nhất của $x$ và $y$ lớn hơn 1.
Bạn được cho một dãy số nguyên dương $A$ gồm $N$ phần tử $A[1], A[2], \ldots, A[N]$. Khoảng cách giữa hai phần tử thứ $i$ và thứ $j$ được định nghĩa là $|i - j|$ (trị tuyệt đối). Với mỗi phần tử thứ $i$ bạn cần tìm cho nó một phần tử thứ $j$ thoả mãn điều kiện sau:
- $1 \le j \le N$; $j \ne i$.
- Cặp $(A[i], A[j])$ là một cặp ước đẹp.
- $|i - j|$ bé nhất.
Dữ liệu nhập:
- Dòng 1 là số nguyên dương $N$ $(1 \le N \le 200000)$.
- Các dòng sau là dãy số nguyên dương $A$ $(1 \le A[i] \le 200000)$.
Kết quả: với mỗi chỉ số $i$ tìm và in ra chỉ số $j$ thích hợp. Nếu có nhiều $j$ thoả mãn hãy chọn $j$ bé nhất. Nếu không tìm thấy $j$ hãy in $-1$.
Ràng buộc: 60% test: $1 \le N \le 2000$; 40% test còn lại: $N \le 200000$.
5
2 3 4 9 173 4 1 2 -1Giải thích ví dụ: $A = [2, 3, 4, 9, 17]$.
- $i = 1$ ($A = 2$): chỉ có $A[3] = 4$ chung thừa số 2 → in 3.
- $i = 2$ ($A = 3$): chỉ có $A[4] = 9$ chung thừa số 3 → in 4.
- $i = 3$ ($A = 4$): ghép được với $A[1] = 2$ → in 1.
- $i = 4$ ($A = 9$): ghép được với $A[2] = 3$ → in 2.
- $i = 5$ ($A = 17$): 17 là số nguyên tố, không ai chia hết cho 17 → in -1.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm thêm đó là toàn bộ tin nhắn của mình với em ấy, để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn. Chúc các bạn học tốt và gặt hái nhiều thành công 😇.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Gợi ýNhìn vào các thừa số nguyên tố
Gợi ý cho em cách giải quyết tối ưu có liên quan đến việc phân tích thừa số nguyên tố nha. Hãy nhìn vào test ví dụ đề cho 5 số: 2, 3, 4, 9, 17. Em hãy phân tích ra thừa số nguyên tố đi:
- Số 2 chỉ có 1 thừa số nguyên tố là 2 thôi, nên tại thừa số nguyên tố 2 em lưu lại vị trí 1 (tức là số tại vị trí 1 có xuất hiện thừa số nguyên tố 2 trong đó).
- Rồi đến số 3, thì tại thừa số nguyên tố 3 lưu vị trí 2.
- Số 4 phân tích ra là $2 \times 2$, xem như chỉ có thừa số nguyên tố 2 thôi, nên tại thừa số nguyên tố 2 em lưu thêm vị trí 3.
- Số 9 phân tích ra là $3 \times 3$, xem như chỉ có thừa số nguyên tố 3, nên tại thừa số nguyên tố 3 em lưu thêm vị trí 4.
- Số 17 phân tích ra là 17, nên tại thừa số nguyên tố 17 em lưu thêm vị trí 5.
Vậy ta có danh sách các thừa số nguyên tố và vị trí xuất hiện của từng số trong dãy như sau:
Em sẽ nhận ra là các vị trí trong từng thừa số nguyên tố luôn tăng dần, bởi vì em xét dãy số từ vị trí đầu tiên đến cuối cùng, số nào có thừa số nguyên tố bao nhiêu thì tại thừa số nguyên tố đó em đưa vị trí đó vào, nên các vị trí sẽ tăng dần.
Anh nói đến đây là rõ lắm á nha. Bài này $A[i]$ tối đa có $200000$, đây là một giá trị nhỏ nên ta có thể sàng nguyên tố Eratosthenes, sau đó tận dụng mảng sàng đó để phân tích thừa số nguyên tố của một số chỉ với độ phức tạp $O(\log)$ thay vì bình thường sẽ phải là $O(\sqrt{n})$. Chi tiết em có thể tham khảo kỹ thuật này trên trang VNOI tại đây: Sàng nguyên tố – VNOI Wiki. Áp dụng kỹ thuật này vào nhé, nếu vẫn chưa ra muốn anh nói rõ thêm nữa thì nhắn lại anh hen.
Kỹ thuậtPhân tích thừa số bằng mảng sàng – O(log)
Khi sàng, thay vì chỉ đánh dấu "là số nguyên tố hay không", ta lưu minPrime[x] = thừa số nguyên tố nhỏ nhất của $x$. Muốn phân tích $x$ thì cứ lặp: lấy $p$ = minPrime[x], ghi nhận $p$, rồi chia $x$ cho $p$. Mỗi lần chia $x$ giảm ít nhất một nửa nên chỉ cần $O(\log x)$ bước.
Vì số lặp lại (như $4 = 2 \times 2$) mình chỉ cần ghi một lần, nên trong code anh dùng thêm biến x nhớ thừa số vừa ghi, gặp lại thì bỏ qua. Em thử bấm chạy từng bước:
Hướng dẫnTìm hàng xóm gần nhất bằng tìm kiếm nhị phân
Ok. Ví dụ như trên sau khi em đã có được thống kê các vị trí phần tử có sự xuất hiện của từng thừa số nguyên tố.
Giả sử giờ khi xét $a[i]$, phân tích ra nó có 3 thừa số nguyên tố là 2, 3, 5 đi ha, và $a[i]$ đó đang ở vị trí 7, tức là $a[7]$. Thì chắc chắn rằng trong danh sách của các thừa số nguyên tố 2, 3, 5 sẽ luôn có vị trí 7 tồn tại và còn thêm nhiều vị trí khác nữa. Giả sử xét thừa số nguyên tố 2 đi: em tìm ra index mà số 7 xuất hiện trong danh sách đó, và xem nó có lân cận trước sau không, tức là idx - 1 và idx + 1, giá trị tại đó đang lưu vị trí số mấy thì thằng ở vị trí đó là cặp số kết hợp được. Cứ thế xét qua hết tất cả thừa số nguyên tố của số mình đang phân tích, tính ra các khoảng cách và chọn ra thằng nhỏ nhất thì đó là đáp án. Còn nếu không tồn tại thằng nào luôn thì xuất ra $-1$.
Như ví dụ mẫu: xét lại $a[1] = 2$, phân tích ra được thừa số nguyên tố 2, tại đó đang có 2 vị trí là 1, 3. Do đang xét $a[1]$ nên ta tìm kiếm nhị phân giá trị 1 trong đó thấy nó tại idx = 0, như thế lân cận với nó là idx + 1 = 1 và tại đó là vị trí 3, có nghĩa là giá trị ở vị trí 3 có thể ghép cặp được với giá trị ở vị trí 1.
- Tạo thống kê các vị trí xuất hiện của từng thừa số nguyên tố (các vị trí đã tăng dần sẵn).
- Xét lại từng số ban đầu, phân tích thừa số nguyên tố của nó.
- Với từng thừa số nguyên tố, tìm kiếm nhị phân vị trí của số đó trong danh sách; thằng liền trước và liền sau chính là 2 vị trí gần nhất với nó (theo thừa số này).
- Gộp qua mọi thừa số:
Max_j= vị trí bên trái gần nhất,Min_k= vị trí bên phải gần nhất. Chọn thằng có khoảng cách nhỏ hơn; nếu bằng nhau thì chọn chỉ số nhỏ hơn, tức là bên trái, đúng như đề yêu cầu. - Không có thằng nào cả thì in $-1$.
Anh nói đến đây là rõ ràng lắm rồi, cố gắng suy ngẫm nha em.
Minh hoạChạy tay toàn bộ thuật toán
Em nhập dãy số (tối đa 14 số, mỗi số từ 1 đến 200000) rồi bấm Tiếp. Giai đoạn 1 xây danh sách vị trí cho từng thừa số nguyên tố, giai đoạn 2 tìm kiếm nhị phân để ra đáp án cho từng $i$:
Thì đụng đến ước số thì ít nhiều luôn có liên quan đến các thừa số nguyên tố em à 😉. Ý tưởng là vậy nhưng mà cũng phải code chắc tay mới ra được đấy, để xem em làm thế nào.
Vậy bây giờ trước tiên em phải làm được cách vét cạn cho bài đó đúng hết ok đi rồi anh mới gửi cho em cách tối ưu, vì anh sẽ khó chấp nhận được nếu cách vét cạn mà em còn làm không được.
Cách 1Vét cạn – loang sang hai bên – O(N²)
Em ấy đã gửi code vét cạn chạy đúng; code ổn có điều chưa clean còn dài quá, nên anh cho em tham khảo code vét cạn của anh (mảng $a$ anh tính index từ 1 nhé). Ý tưởng: từ $i$ đi sang trái tìm $l$ gần nhất có $\gcd(a[i], a[l]) > 1$, đi sang phải tìm $r$ gần nhất tương tự, rồi so khoảng cách. Vì bên trái luôn có chỉ số nhỏ hơn nên khi hoà khoảng cách thì chọn $l$.
#include <bits/stdc++.h>
using namespace std;
vector<int> solve1(int a[], int n){
vector<int> res;
for(int i = 1; i <= n; ++i){
int l = i - 1;
while(l >= 1){
if(__gcd(a[i], a[l]) > 1){
break;
}
l--;
}
int r = i + 1;
while(r <= n){
if(__gcd(a[i], a[r]) > 1){
break;
}
r++;
}
if(l == 0 && r <= n){
res.push_back(r);
}
else if(l >= 1 && r == n + 1){
res.push_back(l);
}
else if(l == 0 && r == n + 1){
res.push_back(-1);
}
else{
if(r - i < i - l){
res.push_back(r);
}
else{
res.push_back(l);
}
}
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n + 1];
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
vector<int> res = solve1(a, n);
for(int x : res){
cout << x << " ";
}
return 0;
}import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + [int(x) for x in data[1:n + 1]] # chỉ số từ 1
res = []
for i in range(1, n + 1):
l = i - 1
while l >= 1 and gcd(a[i], a[l]) == 1:
l -= 1
r = i + 1
while r <= n and gcd(a[i], a[r]) == 1:
r += 1
if l == 0 and r == n + 1:
res.append(-1)
elif l == 0:
res.append(r)
elif r == n + 1:
res.append(l)
else:
# hòa khoảng cách thì chọn l (chỉ số nhỏ hơn)
res.append(r if r - i < i - l else l)
print(*res)
main()Độ phức tạp $O(N^2 \log A)$ trong trường hợp xấu nhất (ví dụ toàn số đôi một nguyên tố cùng nhau), đủ ăn 60% test với $N \le 2000$.
Cách 2Sàng + danh sách vị trí + tìm kiếm nhị phân
Còn code tối ưu AC bài đó thì đây, theo đúng những tư tưởng mà anh đã nhắn em. Xem chỗ nào không hiểu thì anh giải thích cho hen, nhưng mà hãy tự xem thật kỹ nhé vì anh thấy code không khó hiểu. Phần sàng nguyên tố + dựa vào kết quả sàng phân tích ra thừa số nguyên tố với độ phức tạp $O(\log)$ thì anh chép từ nguồn VNOI ở trên nha.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n + 1];
int Max = -1;
for(int i = 1; i <= n; ++i){
cin >> a[i];
Max = max(Max, a[i]);
}
int minPrime[Max + 1] = {0};
for (int i = 2; i * i <= Max; ++i) {
if (minPrime[i] == 0) { //if i is prime
for (int j = i * i; j <= Max; j += i) {
if (minPrime[j] == 0) {
minPrime[j] = i;
}
}
}
}
for (int i = 2; i <= Max; ++i) {
if (minPrime[i] == 0) {
minPrime[i] = i;
}
}
unordered_map<int, vector<int>> mp;
for(int i = 1; i <= n; ++i){
int temp = a[i];
int x = -1;
while (temp != 1) {
if(minPrime[temp] != x){
x = minPrime[temp];
mp[minPrime[temp]].push_back(i);
}
temp /= minPrime[temp];
}
}
for(int i = 1; i <= n; ++i){
int temp = a[i];
int Max_j = -1, Min_k = n + 10;
while (temp != 1) {
int idx = lower_bound(mp[minPrime[temp]].begin(), mp[minPrime[temp]].end(), i) - mp[minPrime[temp]].begin();
if(mp[minPrime[temp]].size() > 1){
if(idx > 0){
Max_j = max(Max_j, mp[minPrime[temp]][idx - 1]);
}
if(idx < mp[minPrime[temp]].size() - 1){
Min_k = min(Min_k, mp[minPrime[temp]][idx + 1]);
}
}
temp /= minPrime[temp];
}
if(Max_j == -1 && Min_k == n + 10){
cout << "-1 ";
}
else if(Max_j == -1 && Min_k != n + 10){
cout << Min_k << " ";
}
else if(Max_j != -1 && Min_k == n + 10){
cout << Max_j << " ";
}
else{
if(Min_k - i < i - Max_j){
cout << Min_k << " ";
}
else{
cout << Max_j << " ";
}
}
}
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + [int(x) for x in data[1:n + 1]]
M = max(a)
# sàng: minPrime[x] = thừa số nguyên tố nhỏ nhất của x
minPrime = list(range(M + 1))
i = 2
while i * i <= M:
if minPrime[i] == i:
for j in range(i * i, M + 1, i):
if minPrime[j] == j:
minPrime[j] = i
i += 1
def factor(x): # các thừa số nguyên tố khác nhau, O(log x)
ps = []
while x != 1:
p = minPrime[x]
ps.append(p)
while x % p == 0:
x //= p
return ps
fac = [None] + [factor(a[i]) for i in range(1, n + 1)]
mp = {} # p -> danh sách vị trí (tăng dần)
for i in range(1, n + 1):
for p in fac[i]:
mp.setdefault(p, []).append(i)
res = []
for i in range(1, n + 1):
L, R = -1, n + 10 # Max_j, Min_k
for p in fac[i]:
pos = mp[p]
if len(pos) > 1:
idx = bisect_left(pos, i)
if idx > 0 and pos[idx - 1] > L:
L = pos[idx - 1]
if idx < len(pos) - 1 and pos[idx + 1] < R:
R = pos[idx + 1]
if L == -1 and R == n + 10:
res.append(-1)
elif L == -1:
res.append(R)
elif R == n + 10:
res.append(L)
else:
res.append(R if R - i < i - L else L)
sys.stdout.write(" ".join(map(str, res)) + "\n")
main()- Sàng:
minPrime[j] = ivới $i$ là số nguyên tố nhỏ nhất chia hết $j$ (chỉ gán lần đầu tiên). Những số còn0sau khi sàng là số nguyên tố, gánminPrime[i] = i. - Xây thống kê:
mp[p]là vector các vị trí có thừa số $p$. Biếnxnhớ thừa số vừa thêm để không thêm trùng (ví dụ số 8 chỉ thêm vàomp[2]đúng 1 lần). - Tìm hàng xóm:
lower_boundtìm ra index của $i$ trongmp[p]; phần tửidx - 1là vị trí bên trái gần nhất,idx + 1là bên phải gần nhất. Lấy max các bên trái (Max_j) và min các bên phải (Min_k). - Chọn đáp án: chỉ chọn bên phải khi nó gần hơn hẳn (
Min_k - i < i - Max_j), còn bằng nhau thì chọn bên trái vì chỉ số nhỏ hơn. - Số $a[i] = 1$ không có thừa số nguyên tố nào nên vòng
whilekhông chạy, kết quả là $-1$. Đúng vì $\gcd(1, y) = 1$.
int minPrime[Max + 1] = {0}; là mảng có kích thước thay đổi (VLA), g++ chấp nhận nhưng không phải C++ chuẩn. Nếu trình biên dịch của em báo lỗi thì đổi thành vector<int> minPrime(Max + 1, 0); là chạy y hệt.Số $\le 200000$ có tối đa 6 thừa số nguyên tố khác nhau ($2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030$), nên với mỗi $i$ ta chỉ tìm kiếm nhị phân vài lần. Tổng các danh sách vị trí cũng chỉ tối đa $6N$ phần tử.
Kiểm chứngChạy so sánh vét cạn và tối ưu
Để chạy kiểm chứng giữa code tối ưu với code vét cạn xem có test nào sai không thì mình random dữ liệu ra cùng chạy với cả 2 code xem có trường hợp nào ra kết quả khác nhau không. Đây là code để chạy check giữa 2 cách: cứ treo tầm 5 phút chạy toàn thấy chữ OK thì là ổn, nếu thấy hiện ra TLE hay WA là không ổn:
Code chạy kiểm chứng (C++)
#include <bits/stdc++.h>
using namespace std;
vector<int> solve1(int a[], int n){
vector<int> res;
for(int i = 1; i <= n; ++i){
int l = i - 1;
while(l >= 1){
if(__gcd(a[i], a[l]) > 1){
break;
}
l--;
}
int r = i + 1;
while(r <= n){
if(__gcd(a[i], a[r]) > 1){
break;
}
r++;
}
if(l == 0 && r <= n){
res.push_back(r);
}
else if(l >= 1 && r == n + 1){
res.push_back(l);
}
else if(l == 0 && r == n + 1){
res.push_back(-1);
}
else{
if(r - i < i - l){
res.push_back(r);
}
else{
res.push_back(l);
}
}
}
return res;
}
vector<int> solve2(int a[], int n){
int Max = a[1];
for(int i = 2; i <= n; ++i){
Max = max(Max, a[i]);
}
int minPrime[Max + 1] = {0};
for (int i = 2; i * i <= Max; ++i) {
if (minPrime[i] == 0) { //if i is prime
for (int j = i * i; j <= Max; j += i) {
if (minPrime[j] == 0) {
minPrime[j] = i;
}
}
}
}
for (int i = 2; i <= Max; ++i) {
if (minPrime[i] == 0) {
minPrime[i] = i;
}
}
unordered_map<int, vector<int>> mp;
for(int i = 1; i <= n; ++i){
int temp = a[i];
int x = -1;
while (temp != 1) {
if(minPrime[temp] != x){
x = minPrime[temp];
mp[minPrime[temp]].push_back(i);
}
temp /= minPrime[temp];
}
}
vector<int> res;
for(int i = 1; i <= n; ++i){
int temp = a[i];
int Max_j = -1, Min_k = n + 10;
while (temp != 1) {
int idx = lower_bound(mp[minPrime[temp]].begin(), mp[minPrime[temp]].end(), i) - mp[minPrime[temp]].begin();
if(mp[minPrime[temp]].size() > 1){
if(idx > 0){
Max_j = max(Max_j, mp[minPrime[temp]][idx - 1]);
}
if(idx < mp[minPrime[temp]].size() - 1){
Min_k = min(Min_k, mp[minPrime[temp]][idx + 1]);
}
}
temp /= minPrime[temp];
}
if(Max_j == -1 && Min_k == n + 10){
res.push_back(-1);
}
else if(Max_j == -1 && Min_k != n + 10){
res.push_back(Min_k);
}
else if(Max_j != -1 && Min_k == n + 10){
res.push_back(Max_j);
}
else{
if(Min_k - i < i - Max_j){
res.push_back(Min_k);
}
else{
res.push_back(Max_j);
}
}
}
return res;
}
int main(){
srand(time(0));
while(1){
int n = 1 + rand() % 2000; // để số nhỏ thôi chứ để đúng như đề bài lớn quá thì cách vét cạn sẽ bị chạy lâu lắm
int a[n + 1];
for(int i = 1; i <= n; ++i){
a[i] = 1 + rand() % 200000;
}
vector<int> res1 = solve1(a, n);
clock_t start = clock();
vector<int> res2 = solve2(a, n);
int timeSolve2 = (clock() - start) * 1000 / CLOCKS_PER_SEC; // đổi ra mili giây
if(res1 == res2 && timeSolve2 <= 1000){
cout << "OK\n";
}
else{
if(timeSolve2 > 1000){
cout << "\nTime Limit Exceeded (TLE):\n";
cout << "Time Solve2 = " << timeSolve2 << " ms";
}
if(res1 != res2){
cout << "\nWrong Answer (WA):\n";
cout << n << endl;
for(int i = 1; i <= n; ++i){
cout << a[i] << " ";
}
cout << "\nres1 = ";
for(int i = 0; i < res1.size(); ++i){
cout << res1[i] << " ";
}
cout << "\nres2 = ";
for(int i = 0; i < res2.size(); ++i){
cout << res2[i] << " ";
}
}
break;
}
}
return 0;
}(clock() - start) * 1000 / CLOCKS_PER_SEC, vì trên Linux clock() đếm theo micro giây chứ không phải mili giây như trên Windows. 2 bản Python là mình viết thêm. Tất cả các bản đã được kiểm tra với 300 bộ test ngẫu nhiên so với vét cạn; với $N = 200000$, bản C++ tối ưu chạy khoảng 0.17 giây, bản Python khoảng 0.75 giây.Đọc chắc cũng mỏi mắt luôn chứ, vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 😅. Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này 🤪.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét