Hướng dẫn giải của [Beginner Free Contest 04] BEGIN 9
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 hai số nguyên dương A và B (B có thể lên tới 10^100000), tìm chữ số tận cùng của A^B.
Sub 1: Vét cạn nhân B lần — ~O(B)~
Nhân A với chính nó B lần, mỗi lần chỉ giữ chữ số cuối (mod 10) để không tràn số. Đúng với các test có B nhỏ (đạt 16/20 test). Với B quá lớn (hơn 18 chữ số) thì vòng lặp không kết thúc kịp (TLE).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string A, B;
cin >> A >> B;
// Sub 1: nhan A voi chinh no B lan, chi giu chu so cuoi (mod 10).
// Neu B co hon 18 chu so thi khong the lap du B lan, nen kep B ve LLONG_MAX
// (khi do vong lap se TLE, khong in ra dap an sai).
long long b = B.size() > 18 ? LLONG_MAX : stoll(B);
long long a = A.back() - '0';
long long res = 1;
for (long long i = 0; i < b; i++) res = res * a % 10;
cout << res << endl;
return 0;
}
Sub 2: Chu kỳ của chữ số tận cùng — ~O(1)~
Chữ số tận cùng của A^B chỉ phụ thuộc vào chữ số tận cùng của A (gọi là a) và B.
- Nếu a ∈ {0, 1, 5, 6} thì a^B luôn có chữ số tận cùng là a.
- Với a ∈ {2, 3, 7, 8} thì chữ số tận cùng lặp chu kỳ 4 theo số mũ, nên chỉ cần B mod 4.
Vì B rất lớn nên không đọc thành số nguyên được. Ta đọc B dưới dạng chuỗi và tính B mod 4 bằng hai chữ số cuối (vì 100 chia hết cho 4). Khi B mod 4 = 0 thì dùng số mũ 4, vì B ≥ 1. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Tinh (base mod 10) ^ e voi e nho
int powmod10(int base, int e) {
int r = 1;
for (int i = 0; i < e; i++) r = r * base % 10;
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// A va B co the len toi 10^100000, nen doc dang chuoi
string A, B;
cin >> A >> B;
int a = A.back() - '0'; // A mod 10 lay tu chu so cuoi
// Chu so cuoi cua a^B lap lai voi chu ky 4 (voi a = 2,3,7,8) hoac 1 (a = 0,1,5,6)
// B mod 4 tinh tu 2 chu so cuoi cua B
int bmod4 = (B.size() >= 2 ? (B[B.size() - 2] - '0') * 10 + (B.back() - '0') : (B.back() - '0')) % 4;
if (a == 0 || a == 1 || a == 5 || a == 6) {
cout << a << endl; // luy thua giu nguyen chu so cuoi
} else {
int e = bmod4 == 0 ? 4 : bmod4; // B >= 1 nen khi chia het cho 4 thi e = 4
cout << powmod10(a, e) << endl;
}
return 0;
}
Bình luận