Hướng dẫn giải của [200 đề thầy Đức] Bài 82: Số lượng ước số chung
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Đếm số nguyên dương ~x~ là ước chung của mọi phần tử trong dãy.
Sub 1: Thử từng x — ~O(n \cdot \min(a))~, dùng khi ~\min(a) \le 1000~
Với ~x~ từ 1 đến ~\min(a)~, kiểm tra ~x~ có chia hết mọi phần tử không rồi đếm.
Nếu chỉ nộp sub này: đúng 6/21 test.
Sub 2: Đếm ước của UCLN — ~O(n + \sqrt{g})~, dùng khi mọi trường hợp còn lại
Một số là ước chung của cả dãy khi và chỉ khi là ước của ~g = \text{UCLN}(a_1, \dots, a_n)~. Đếm ước của ~g~ bằng cách duyệt ~i \le \sqrt{g}~, mỗi ước ~i~ tính thêm ~g/i~. Giá trị ~g~ đến ~10^{12}~ nên dùng số nguyên 64 bit.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng dãy. Nếu phần tử nhỏ nhất không vượt quá 1000 thì gọi sub1, ngược lại gọi sub2. Ví dụ: dãy ~2, 4, 6, 2, 10~ cho 2; dãy ~6, 90, 12, 18, 30, 18~ cho 4.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: vet can. Thu tung x = 1..min(a), kiem tra x chia het moi phan tu. O(n * min(a)), dung khi min(a) <= 1000.
void sub1() {
long long mn = *min_element(a.begin(), a.end());
long long cnt = 0;
for (long long x = 1; x <= mn; x++) {
bool ok = true;
for (long long v : a)
if (v % x != 0) {
ok = false;
break;
}
if (ok) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: x la uoc chung cua day <=> x la uoc cua g = UCLN(a1..an).
// Dem uoc cua g bang cach duyet i den can(g). O(sqrt(g)), g <= 10^12.
void sub2() {
long long g = 0;
for (long long v : a) g = __gcd(g, v);
long long cnt = 0;
for (long long i = 1; i * i <= g; i++)
if (g % i == 0) {
cnt++;
if (i != g / i) cnt++;
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
a.assign(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
if (*min_element(a.begin(), a.end()) <= 1000) sub1();
else sub2();
}
return 0;
}
Bình luận