SPOJ.COM – Thuật toán bài LASTDIG - The last digit
Đề bài:
Nestor đã làm công việc của lớp toán khoảng 3 ngày rồi. Tuy nhiên, anh ấy rất mệt vì phải làm rất nhiều công việc. Do đó, anh ấy nên chuyển giao công việc vào ngày mai. Giáo viên toán đưa cho anh ta 2 số a và b.
Bài toàn đặt ra là tìm ra chữ số cuối cùng của phép toán a^b (a mũ b). Hãy giúp anh ấy bài toán này. Bạn được đưa cho 2 số nguyên là a (0 <= a <= 20) và b (0 <= b <= 2,147,483,000), với a và b không được cùng bằng 0.
Đầu vào:
Dòng đầu tiên là số nguyên t, số lượng test case, t <= 30. Sau đó là t test case, mỗi cái sẽ trên một dòng và bao gồm 2 số nguyên a, b cách nhau bằng dấu cách.
Đầu ra:
Mỗi test case in ra trên 1 dòng là số cần tìm.
Ví dụ:
Đầu vào:
2
3 10
6 2
Đầu ra:
9
6
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/LASTDIG/
Phân tích:
-
Tôi sẽ sử dụng thuật toán tham lam Greedy để giải bài toán.
-
Vì đề bài yêu cầu tìm chữ số cuối cùng nên thực chất tôi chỉ cần quan tâm đến chữ số hàng đơn vị của số a, giả sử là x. Tức là nếu cần tìm chữ số cuối cùng của 13^b thì tôi sẽ tìm chữ số cuối cùng của 3^b. Kết quả là giống nhau.
-
Tiếp theo, tôi sẽ xử lý số b. Số b có giá trị lớn nhất là 2,147,483,000, nên tôi không thể tính trực tiếp được. Tuy nhiên nếu các bạn chịu khó viết ra lũy thừa của các số từ 1 đến 9. Các bạn sẽ thấy rằng chữ số cuối cùng của kết quả sẽ lặp lại với chu kì bằng 4. Nghĩa là chữ số cuối cùng của a^b = chữ số cuối cùng của a^(b + 4). Do đó, thực chất tôi chỉ cần lấy số dư của b cho 4, giả sử là y.
-
Vậy chữ số cuối cùng của a^b sẽ bằng chữ số cuối cùng của x^y. Cụ thể mời bạn theo dõi code bên dưới.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include <iostream> | |
| using namespace std; | |
| int power(int a, int b) | |
| { | |
| if (b == 0) return 1; | |
| if(b % 2 == 0) | |
| { | |
| int t = power(a, b/2); | |
| return t*t; | |
| } | |
| else | |
| { | |
| int t = power(a, (b - 1) / 2); | |
| return t*t*a; | |
| } | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); | |
| freopen("input.txt","r",stdin); | |
| int T; | |
| unsigned int a, b; | |
| int last_digit; | |
| cin >> T; | |
| for(int tc = 0; tc < T; tc++) | |
| { | |
| cin >> a >> b; | |
| if(b == 0) last_digit = 1; | |
| else | |
| { | |
| int x = a % 10; | |
| int y = b % 4; | |
| if (y == 0) y = 4; | |
| last_digit = power(x, y) % 10; | |
| } | |
| cout << last_digit << endl; | |
| } | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.