Hướng dẫn giải của Thi thử HSG9 2026 - Ngày 2 - Số hài hòa
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ả:
Trong bài toán này, bằng thực nghiệm, ta có thể chạy thử code duyệt từ ~36~ tới ~10^9~, mỗi bước tăng ~36~ đơn vị. Việc tính tổng và tích chữ số ta tạm thời tính trâu.
Nhận xét: code sẽ chạy trong khoảng ~20~ giây, và có khoảng ~2500~ số thỏa mãn. Điều này cho phép ta sinh ra mọi số thỏa mãn.
Đến đây, để cải tiến, ta có 2 cách:
- Ta sinh mảng hằng, viết hết ~2500~ số vào code để tiến hành trả lời truy vấn.
- Ta cần cải tiến việc tính tổng và tích các chữ số. Ta có thể làm như sau:
- Với mọi số từ ~1~ tới ~10^7~, ta tiền xử lý trước với công thức: ~f_i~ là tổng chữ số của ~i~, thì ~f_i = f_{i / 10} + i \% 10~. Tương tự với tích chữ số.
- Với các số ~> 10^7~, để tính tổng và tích chữ số, ta chỉ cần bỏ tối đa hai chữ số cuối cùng, sau đó ta dựa vào hai mảng ta đã tính trước. Độ phức tạp mỗi lần trở về gần như ~O~ ~(1)~.
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"
const int N = 1e8 + 9;
const int inf = 2e18;
int sumDig[N / 10];
int proDig[N / 10];
int sum_dig (int n){
int sum = 0;
while (n > 0){
if (n < N / 10) return sum + sumDig[n];
sum += n % 10; n /= 10;
}
return sum;
}
int pro_dig (int n){
int sum = 1;
while (n > 0){
if (n < N / 10) return sum * proDig[n];
sum *= n % 10; n /= 10;
}
return sum;
}
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
for (int i = 1; i < N / 10; i++){
if (i <= 9){
sumDig[i] = proDig[i] = i; continue;
}
sumDig[i] = sumDig[i / 10] + (i % 10);
proDig[i] = proDig[i / 10] * (i % 10);
}
vector <int> vals;
for (int i = 36; i <= 1e9; i += 36){
if (pro_dig (i) != 0 && i % (sum_dig (i) + pro_dig (i)) == 0) vals.push_back (i);
}
int q; cin >> q;
while (q--){
int res = 0;
int l, r; cin >> l >> r;
res = upper_bound (vals.begin (), vals.end (), r) - lower_bound (vals.begin (), vals.end (), l);
cout << res << "\n";
}
}
// <33
Bình luận