Hướng dẫn giải của [VT Thiếu nhi] BÀI 28: AMSTRONG
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
Số Amstrong là số x mà tổng lũy thừa bậc k (k là số chữ số của x) của các chữ số bằng chính x. Cần liệt kê mọi số như vậy từ 0 đến n, mỗi số một dòng tăng dần. Với n ≤ 10^6 nên duyệt từng số là đủ.
Sub 1: Vét cạn, tính lũy thừa bằng phép nhân — ~O(n·log n)~
Với mỗi x từ 0 đến n: đếm số chữ số k, rồi với mỗi chữ số d tính d^k bằng cách nhân k lần, cộng dồn và so sánh với x. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("AMSTRONG.INP", "r")) { freopen("AMSTRONG.INP", "r", stdin); freopen("AMSTRONG.OUT", "w", stdout); }
long long n;
cin >> n;
// Vét cạn: với mỗi x từ 0 đến n, đếm số chữ số k và cộng a^k của từng chữ số bằng phép nhân
for (long long x = 0; x <= n; x++) {
int k = 0;
long long t = x;
do { k++; t /= 10; } while (t > 0);
long long sum = 0;
t = x;
do {
int d = t % 10;
long long p = 1;
for (int i = 0; i < k; i++) p *= d; // d^k bằng cách nhân k lần
sum += p;
t /= 10;
} while (t > 0);
if (sum == x) cout << x << "\n";
}
return 0;
}
Sub 2: Bảng lũy thừa tra sẵn — ~O(n·log n)~
Vì x ≤ 10^6 có tối đa 7 chữ số nên tính trước bảng pw[d][k] = d^k (d từ 0 đến 9, k từ 0 đến 7). Khi duyệt chỉ cần tra bảng, không phải nhân lại. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("AMSTRONG.INP", "r")) { freopen("AMSTRONG.INP", "r", stdin); freopen("AMSTRONG.OUT", "w", stdout); }
long long n;
cin >> n;
// Với x <= 10^6 có tối đa 7 chữ số, nên tính trước bảng pw[d][k] = d^k (d = 0..9, k = 0..7)
long long pw[10][8];
for (int d = 0; d <= 9; d++) {
pw[d][0] = 1;
for (int k = 1; k <= 7; k++) pw[d][k] = pw[d][k - 1] * d;
}
for (long long x = 0; x <= n; x++) {
// Đếm số chữ số
int k = 0;
long long t = x;
do { k++; t /= 10; } while (t > 0);
// Tổng lũy thừa bậc k của các chữ số
long long sum = 0;
t = x;
do {
sum += pw[t % 10][k];
t /= 10;
} while (t > 0);
if (sum == x) cout << x << "\n";
}
return 0;
}
Bình luận