Hướng dẫn giải của Tìm số (đề HSG 9 Phú Thọ 2015-2016)
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 số nguyên dương n (tối đa 10^5 chữ số), cộng các chữ số cho đến khi còn một chữ số. Đọc n dưới dạng chuỗi vì có thể rất dài. Đọc từ TIMSO.INP, ghi ra TIMSO.OUT.
Sub 1: Mô phỏng đúng đề — ~O(L·k)~
Lặp: cộng các chữ số của chuỗi hiện tại, đổi tổng thành chuỗi mới, cho đến khi chuỗi chỉ còn một ký tự. Mỗi vòng giảm độ dài đáng kể nên số vòng ít. Cách này đúng với mọi test.
Kết quả chấm: đạt 32/32 test (SUB ok 32/32, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("TIMSO.INP", "r")) {
freopen("TIMSO.INP", "r", stdin);
freopen("TIMSO.OUT", "w", stdout);
}
// n có thể rất dài nên đọc dưới dạng chuỗi
string s;
cin >> s;
// Mô phỏng đúng đề: cộng các chữ số cho đến khi còn một chữ số
while (s.size() > 1) {
long long tong = 0;
for (char c : s) tong += c - '0';
s = to_string(tong);
}
cout << s << "\n";
return 0;
}
Sub 2: Công thức đồng dư 9 — ~O(L)~
Tổng các chữ số của n đồng dư với n theo modulo 9, và phép cộng chữ số lặp lại giữ nguyên số dư này. Vậy kết quả là (tổng chữ số) mod 9, với quy ước: nếu số dư bằng 0 (và n > 0) thì kết quả là 9. Chỉ cần một lần duyệt chuỗi, không cần lặp.
Kết quả chấm: đạt 32/32 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("TIMSO.INP", "r")) {
freopen("TIMSO.INP", "r", stdin);
freopen("TIMSO.OUT", "w", stdout);
}
// n có tới 10^5 chữ số nên đọc dưới dạng chuỗi
string s;
cin >> s;
// Tổng các chữ số của n đồng dư n (mod 9); kết quả cuối là "gốc số học":
// 1..9 tương ứng với n mod 9 (với 9 khi n chia hết cho 9)
long long tong = 0;
for (char c : s) tong += c - '0';
long long kq = tong % 9;
if (kq == 0) kq = 9;
cout << kq << "\n";
return 0;
}
Bình luận