Hướng dẫn giải của [Ninh Bình - TS10 - 2024] Bài 1: Ước số
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.
Tác giả:
Trước hết, ta sẽ duyệt tất cả các phần tử ~a_i~ trong mảng để xem số ước lớn nhất thu được từ ~a_i~ là bao nhiêu.
Gọi số ước lớn nhất thu được từ ~a_i~ là ~x~. Ta lại duyệt mảng ~a~ thêm một lần nữa để tìm vị trí ~i~ đầu tiên mà số ước của ~a_i~ đúng bằng ~x~.
ĐPT: ~O~(~n \times \sqrt{n}~)
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int a[N];
int n;
int solve(int x) {
int ret = 0;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0 and i * i != x) {
ret += 2;
}
if (i * i == x) {
++ret;
}
}
return ret;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int mx = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, solve(a[i]));
}
for (int i = 1; i <= n; i++) {
if (solve(a[i]) == mx) {
cout << a[i];
return 0;
}
}
}
// <33
Bình luận