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

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

• Mình 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 mình 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ì mình sẽ tìm chữ số cuối cùng của 3^b. Kết quả là giống nhau.

• Tiếp theo, mình sẽ xử lý số b. Số b có giá trị lớn nhất là 2,147,483,000, nên mình không thể tính trực tiếp được. Tuy nhiên nếu bạn chịu khó viết ra lũy thừa của các số từ 1 đến 9. 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 mình 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

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 mình 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 mình 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 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;
}