Tìm thừa số trước khi thực hiện phép nhân với mod

A = (A * B) % MOD. đã biết B và A sau khi MOD. làm thế nào để tìm lại A trước khi MOD với MOD = 1e9 + 7

tính A = (A / B) % MOD là được :relieved:

vì MOD ở đây là số nguyên tố nên có thể tính A / B = A * B^-1. Tính B^-1 thì dựa vào định lý Fermat nhỏ a^p \equiv a \mod p có thể tính a^{p-2} \equiv a^{-1} \mod p

vậy tính A = (A * (B^(MOD-2))) % MOD là được

6 Likes

Điều kiện là UCLN(B, MOD) = 1 để thực hiện nghịch đảo.

Cách chuẩn là dùng thuật toán Euclid mở rộng: kèm theo hai biến chạy ab ta tính (x_a, y_a) là một nghiệm nguyên của a_0x_a + b_0y_a = a_{\text{hiện tại}}(x_b, y_b) tương tự.

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