Hướng dẫn giải của Số chính phương (đề Lào Cai 2021)
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
Bước 1: tính tổng S các chữ số của N (N ≤ 10^18 nên dùng long long, tổng chữ số tối đa là 18·9 = 162).
Bước 2: nếu S là số chính phương thì in S; nếu không thì in S chia dư cho 11.
Sub 1: Thử mọi k để kiểm tra chính phương — ~O(\sqrt{S})~
Với S nhỏ (không quá 162), thử lần lượt các số k = 0, 1, 2, ... cho đến khi k·k > S; nếu có k·k = S thì S là số chính phương.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("Cau2a.inp", "r")) {
freopen("Cau2a.inp", "r", stdin);
freopen("Cau2a.out", "w", stdout);
}
long long n;
cin >> n;
// Tổng các chữ số của N (N <= 10^18 nên đủ long long)
long long s = 0;
for (long long t = n; t > 0; t /= 10) s += t % 10;
// Vét cạn: thử mọi k để xem s có phải bình phương của một số nguyên không
bool chinhPhuong = false;
for (long long k = 0; k * k <= s; k++)
if (k * k == s) chinhPhuong = true;
if (chinhPhuong) cout << s << "\n";
else cout << s % 11 << "\n";
return 0;
}
Sub 2: Căn bậc hai — ~O(1)~
Lấy căn bậc hai của S rồi điều chỉnh r sao cho r² ≤ S < (r+1)²; khi đó S là số chính phương khi và chỉ khi r² = S. Với S nhỏ, số thực không có sai số đáng kể nhưng vẫn kiểm tra lại bằng hai vòng while.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("Cau2a.inp", "r")) {
freopen("Cau2a.inp", "r", stdin);
freopen("Cau2a.out", "w", stdout);
}
long long n;
cin >> n;
// Tổng các chữ số của N (tối đa 18 * 9 = 162)
long long s = 0;
for (long long t = n; t > 0; t /= 10) s += t % 10;
// Kiểm tra s có phải số chính phương: lấy căn bậc hai làm tròn rồi kiểm tra lại
long long r = (long long)sqrt((double)s);
while (r * r > s) r--;
while ((r + 1) * (r + 1) <= s) r++;
bool chinhPhuong = (r * r == s);
// Nếu là số chính phương in tổng, không thì in tổng chia dư 11
if (chinhPhuong) cout << s << "\n";
else cout << s % 11 << "\n";
return 0;
}
Bình luận