Hướng dẫn giải của Ước số chung đặc biệt (đề HSG 12 Phú Thọ 2023-2024)
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
Ước chung đặc biệt của ~a~ và ~b~ là ước chung có tổng chữ số lớn nhất. Đầu ra là tổng chữ số của ước đó. Ước chung của ~a~ và ~b~ chính là ước của ~\gcd(a, b)~.
Sub 1: Thử mọi d — ~O(\min(a, b))~, dùng khi ~\min(a, b) \le 10^6~
Duyệt ~d~ từ 1 đến ~\min(a, b)~, nếu ~d~ chia hết cả ~a~ và ~b~ thì xét tổng chữ số của ~d~.
Nếu chỉ nộp sub này: đúng 18/20 test.
Sub 2: Ước của gcd — ~O(\sqrt{\gcd(a, b)})~
Đặt ~g = \gcd(a, b)~. Liệt kê ước của ~g~ bằng cách thử ~i \le \sqrt{g}~, lấy cả ~i~ và ~g/i~, lấy tổng chữ số lớn nhất.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
long long a, b;
int digitSum(long long x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: vét cạn — thử mọi d từ 1 đến min(a, b); d là ước chung thì xét tổng chữ số. O(min(a, b))
void sub1() {
long long mn = min(a, b);
int best = 0;
for (long long d = 1; d <= mn; d++)
if (a % d == 0 && b % d == 0) best = max(best, digitSum(d));
cout << best << "\n";
}
// Sub 2: ước chung của a và b chính là ước của g = gcd(a, b).
// Liệt kê ước của g bằng cách thử i <= sqrt(g) (lấy cả i và g/i). O(sqrt(g))
void sub2() {
long long g = __gcd(a, b);
int best = 0;
for (long long i = 1; i * i <= g; i++) {
if (g % i == 0) {
best = max(best, digitSum(i));
best = max(best, digitSum(g / i));
}
}
cout << best << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> a >> b;
if (min(a, b) <= 1000000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận