Lấy dư của số lớn với 1 số nhỏ hơn 10^6

Tan_Kiem · July 6, 2019, 7:09am

e có 1 bài tập tính số dư: a%m
với a là 1 số có thể có 10^6 chữ số.
m là 1 số tự nhiên nhỏ hơn 10^6.
Cho e hỏi thuật toán với ạ.

rogp10 · July 6, 2019, 7:11am

Sơ đồ Horner khá dễ vì modulo ko quá 1 word.

kisuluoibieng · July 6, 2019, 7:51am

có một ý tưởng thế này
giá trị của a đó lưu vào 1 mảng theo từng block (9 số chẳn hạn, có thể lớn hơn, càng lớn càng nhanh nhưng kiểu dữ liệu phải chứa được số lớn như vậy), block cắt từ sau ra trước
giả sử 123456789123456789123%987654
ta có arr = [123, 456789123, 456789123]
viết bằng python 3 cho gọn

# input tự xử
base = 10**9
t = 0
while len(arr) > 0:
    t = (t*base + arr.pop(0)) % m
# kết quả cuối cùng là t
print(t)

nếu bạn không cắt thành block tùy chọn được thì cứ chia thành mảng arr = [1,2,3,4,5…] thôi, khi đó block là 1, base = 10**1 = 10

Phong_Ky_Vo · July 8, 2019, 6:30am

Hi newbie.
Cho mình hỏi bạn định dùng nó để làm gì ? Nếu chỉ là lập trình code v.v… thì dùng luông % Nếu bạn cần phát triển một tuật toán đặc thù thì có thể tìm các tài liệu liên quan hoặc hỏi người hướng dẫn. Nhưng về cơ bản đây là thuật toán kinh điển nên sẽ có tài liệu thôi hoặc lib.