Tìm chữ số cuối cùng của a^b

nguyenhieuckt · February 25, 2019, 3:44am

Đề bài : Cho 2 số nguyên dương a và b, hãy tìm chữ số cuối cùng của a^b.
Hỏi: Em dùng vòng for từ 1->b và nhân cho a. Sau đó lại chia lấy dư nhưng chỉ được 15/50đ. Em đọc thấy mấy ac dùng getline gì đó e không hiểu. Ai cho em cách tốt hơn được không ạ?

rogp10 · February 25, 2019, 3:03am

Bài này dùng bình phương - nhân

a^2k = (a^k)²

lonelyboy.vh4 · February 25, 2019, 3:06am

bài này bạn cho 1 số cụ thể và viết ra sẽ thấy chữ số cuối cùng có qui luật tuần hoàn. vd a = 3: 3⁰ = 1, 3¹= 3, 3²= 9, 3³= 27, 3⁴ = 81, 3⁵= 243, 3⁶ = 729, … Qui luật tuần hoàn các chữ số cuối cùng là 1, 3, 9, 7. Từ đó với số b cụ thể, bạn có thể dễ dàng tính ra.

Panda9x · February 25, 2019, 3:13am

Chữ số cuối cùng của a^b = (a%10)^b%10. Không biết đúng không nhỉ?

rogp10 · February 26, 2019, 4:34am

Số mũ mod 4 chứ phi(10) = 4.

Thực ra mod 2 có chu kì 1 (vì {1}) và mod 5 có chu kì 4.

hungaya · February 25, 2019, 1:03pm

Chuyển từ tập số nguyên Z sang Z/10Z tính toán dễ hơn, chỉ cần kết hợp thêm 2 mệnh đề sau:

Mệnh đề 1:
Với n là số nguyên dương, x thuộc { 0, 1, 5, 6 }, xⁿ = x, hay:
0ⁿ = 0, 1ⁿ = 1, 5ⁿ = 5, 6ⁿ = 6.

Mệnh đề 2:
Với mọi x thuộc Z/10Z nhưng không thuộc { 0, 1, 5, 6 }, luôn tồn tại số nguyên dương p sao cho x^p = q, với q thuộc { 1, 6 }.

Ví dụ: tìm chữ số cuối cùng của 172¹⁰⁷
Vì 172 = 2 (Z/10Z), nên 172¹⁰⁷ = 2¹⁰⁷.
Ta có 2¹⁰⁷ = 2^{4.26 + 3} = (2⁴)²⁶ . 2³.

Do 16 = 6 trên Z/10Z nên 16²⁶ = 6²⁶ = 6 (theo mệnh đề 1)
Mặc khác 16²⁶ = (2⁴)²⁶, nên (2⁴)²⁶ = 6.

Ngoài ra, ta có 2³ = 8.

Tóm lại:
172¹⁰⁷ = 2¹⁰⁷ = (2⁴)²⁶ . 2³ = 6.8 = 48 = 8.

Red_Sand · February 25, 2019, 4:06pm

Xin chào, bạn có thể cho xin trang web test đề đó được không ạ, mình thử test cách của mình.

nguyenhieuckt · February 26, 2019, 3:47am

mình nhớ là của freecontest nào đấy. sr không có test

Red_Sand · February 26, 2019, 4:10pm

Vậy tại sao bạn lại biết bạn được 15/50 điểm? Test này từ lâu trước đây? Bạn có thể nhớ lại tên của contesst không :((

nguyenhieuckt · February 27, 2019, 1:13pm

https://drive.google.com/drive/folders/19t9fJJ88VxElJG1loWqmuL6Hb_ZtdfRT?fbclid=IwAR0T-SMlbWi0AL9h_sEXCEv-e0CDTPVaEJwIlihicwWh-bPR8BT_XjGf3uk bài begin nha bạn

rogp10 · February 27, 2019, 5:12pm

10^100000 thì… đúng là phải mod 4 thôi O(1) luôn.

Dàn này mỗi bài INCPOS ko phải là beginner

Red_Sand · February 27, 2019, 4:58pm

There you go.
python 3

def LastDigit(a = 0, b = 0):
	a %= 10;
	res = 1;
	while b > 0:
		if b & 1:
			res = (res * a)%10
		a = (a*a)%10
		b >>= 1
	return res