Hỏi cách hoạt động của code tính lũy thừa lấy mod

#1

Đề của bài là viết chương trình tính lũy thừa của hai số nguyên dương

INPUT

Hai số nguyên m và n

OUTPUT

Số dư còn lại khi lấy lũy thừa mn chia cho giá trị 1.000.000.007

Link chương trình

Em hỏi được một bạn bài này nhưng nó giải thích xong em vẫn không hiểu lắm ạ .Em là sinh viên năm nhất mới học c++ nên mong thông cảm và được chỉ giáo ạ , em xin cảm ơn

#2

em ko hiểu chỗ nào :V

mà code sai nữa kìa :V

2 Likes
#3

cả tác giả giải thích cho mà bạn cũng không hiểu, bạn đi hỏi người khác tức là bạn nghĩ người khác hiểu code đó hơn tác giả?
Sao bạn không nghĩ không hiểu là do bạn chưa đủ kiến thức để hỏi bài đó và bắt đầu học?

2 Likes
#4

để tính nhanh ví dụ S = a + a + a + … + a, tổng cộng n lần, thì ta có thể tính nhanh như thế này:

  • nếu n chẵn, hay n = 2k, ta tính tổng S’ = a + a + … + a (k lần), rồi tính tổng S = S’ + S’, vậy là từ (n-1) phép cộng ta giảm còn (k - 1 + 1) = k phép cộng
  • nếu n lẻ, hay n = 2k + 1, ta tính tổng S’ = a + a + … + a (k lần), rồi tính tổng S = S’ + S’ + a (S’ là tổng k số a, 2S’ là 2k số a, thêm 1 số a nữa là 2k + 1 = n số a = S), vậy là từ (n-1) phép cộng ta giảm còn (k - 1 + 1 + 1) = (k+1) = phép cộng

nhưng để tính tổng S’ thì ta lại có thể làm tương tự, tính tổng S’’ = k/2 số a hoặc (k-1)/2 số a là được, rồi để tính S’’ ta có thể tính S’’’, v.v… mỗi lần như vậy ta chỉ cần 1 hoặc 2 phép cộng là được Si’

có bao nhiêu S’ S’’ S’’’… như vậy? Câu trả lời là log2n. Vì khi k = 1 ta ko cần tính phép cộng nào nữa, vậy ta dừng khi k = 1. Với S’ k = n/2, S’’ k = n/4, S’’’ k = n/8 … S cuối cùng sẽ có k = n / 2i. Mà k ở đây = 1, hay n / 2i = 1 hay n = 2i, hay i = log2n

vậy từ n-1 phép cộng ta giảm còn tối đa 2log2n phép cộng :V

ví dụ n = 1 tỷ lẻ 1, thay vì tính 1 tỷ lần phép cộng, ta chỉ cần tính tối đa 2log2(1 tỷ lẻ 1) = 60 phép cộng là đủ @_@ Tính chính xác thì

1. S(1000000001) = 2 phép cộng: S(500000000) + S(500000000) + a
2. S(500000000) = 1 phép cộng: S(250000000) + S(250000000)
3. S(250000000) = 1 phép cộng: S(125000000) + S(125000000)
4. S(125000000) = 1 phép cộng: S(62500000) + S(62500000)
5. S(62500000) = 1 phép cộng: S(31250000) + S(31250000)
6. S(31250000) = 1 phép cộng: S(15625000) + S(15625000)
7. S(15625000) = 1 phép cộng: S(7812500) + S(7812500)
8. S(7812500) = 1 phép cộng: S(3906250) + S(3906250)
9. S(3906250) = 1 phép cộng: S(1953125) + S(1953125)
10. S(1953125) = 2 phép cộng: S(976562) + S(976562) + a
11. S(976562) = 1 phép cộng: S(488281) + S(488281)
12. S(488281) = 2 phép cộng: S(244140) + S(244140) + a
13. S(244140) = 1 phép cộng: S(122070) + S(122070)
14. S(122070) = 1 phép cộng: S(61035) + S(61035)
15. S(61035) = 2 phép cộng: S(30517) + S(30517) + a
16. S(30517) = 2 phép cộng: S(15258) + S(15258) + a
17. S(15258) = 1 phép cộng: S(7629) + S(7629)
18. S(7629) = 2 phép cộng: S(3814) + S(3814) + a
19. S(3814) = 1 phép cộng: S(1907) + S(1907)
20. S(1907) = 2 phép cộng: S(953) + S(953) + a
21. S(953) = 2 phép cộng: S(476) + S(476) + a
22. S(476) = 1 phép cộng: S(238) + S(238)
23. S(238) = 1 phép cộng: S(119) + S(119)
24. S(119) = 2 phép cộng: S(59) + S(59) + a
25. S(59) = 2 phép cộng: S(29) + S(29) + a
26. S(29) = 2 phép cộng: S(14) + S(14) + a
27. S(14) = 1 phép cộng: S(7) + S(7)
28. S(7) = 2 phép cộng: S(3) + S(3) + a
29. S(3) = 2 phép cộng: S(1) + S(1) + a
Tổng = 42 phép cộng

thay phép cộng bằng phép nhân thì ta có cách tính lẹ ab ko cần nhân b-1 lần, chỉ cần nhân tối đa 2logb lần :V

có thêm mod m thì vẫn xài cách nhân này được, vì (ab) mod m = ((a mod m) * (b mod m)) mod m. Chứng minh:

  • giả sử a chia m = a’ dư r1, b chia m = b’ dư r2. Vậy a = a’m + r1, b = b’m + r2.
  • ta có (ab) = a’b’m2 + (a’r2 + b’r1)m + r1r2 = (a’b’m + a’r2 + b’r1)m + r1r2
  • vì a’, b’, m, r1, r2 là số nguyên nên (a’b’m + a’r2 + b’r1) cũng là 1 số nguyên nào đó, đặt số đó là k.
  • vậy ab = km + r1r2, hay số dư của phép chia ab cho m = số dư của phép chia r1r2 cho m (vì km chia hết cho m)
  • mà r1 là số dư của phép chia a cho m, r2 là số dư của phép chia b cho m
  • vậy (ab) mod m = (r1r2) mod m = ((a mod m) * (b mod m)) mod m

ví dụ
a10001 mod m = {[(a5000 mod m) * (a5000 mod m)] mod m} * a mod m
a5000 mod m = [(a2500 mod m) * (a2500 mod m)] mod m
v.v…

code trong link kia là tính ngược từ dưới lên thôi :V

tính ngược từ dưới lên theo nguyên tắc này:

  • viết b dưới dạng số nhị phân. Ví dụ b=123 thì dạng nhị phân là (1111011)2
  • cho i đi từ 0 lên: nếu bi = 1 thì thêm số hạng 2i vào tổng của b. Vd: 123 = 20 + 21 + 23 + 24 + 25 + 26 = 1 + 2 + 8 + 16 + 32 + 64.
  • vậy ab = a1 + 2 + 8 + 16 + 32 + 64 = a1a2a8a16a32a64
  • vậy ta cần tính a1, a2, a8, a16, a32, a64 rồi nhân vào là đủ :V
  • tính a2^i dễ dàng: a1, a1a1=a2, a2a2 = a4, a4a4 = a8, …
5 Likes
#5

cảm ơn bạn rất nhiều <3

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?