Hướng dẫn giải của Câu 2 (Tuyển sinh chuyên Tin Bình Dương 2022-2023)
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
Cho N bạn nữ và M bạn nam (N, M ≤ 10^5). Chia đều các bạn vào nhiều tổ nhất có thể, mỗi tổ có số nữ bằng nhau và số nam bằng nhau.
Sub 1: Vét cạn, thử từ lớn xuống — ~O(\min(N, M))~
Thử số tổ d từ min(N, M) xuống 1, lấy d đầu tiên chia hết cả N và M.
Kết quả chấm: 20/40 (SUB ok 20/40, TLE 20, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
// Vet can: thu lan luot cac so d tu min(n, m) xuong 1, lay d dau tien chia het ca n va m
long long d = min(n, m);
while (d > 1 && (n % d != 0 || m % d != 0)) d--;
cout << d << "\n" << n / d << " " << m / d << "\n";
return 0;
}
Sub 2: Ước chung lớn nhất — ~O(\log(\min(N, M)))~
Số tổ nhiều nhất chính là ƯCLN(N, M) = g. Mỗi tổ có N / g bạn nữ và M / g bạn nam.
Kết quả chấm: 40/40
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
// So to lon nhat chinh la UCLN(n, m); moi to co n/g ban nu va m/g ban nam
long long g = __gcd(n, m);
cout << g << "\n" << n / g << " " << m / g << "\n";
return 0;
}
Bình luận