Thắc mắc về thuật toán (a^b)%c

hunghinh2000 · January 4, 2019, 8:28am

Mình đang tìm hiểu về thuật toán Modular Exponentiation (a^b)%c, và công thức thường dùng để giải quyết là: ((a%c)*(b%c))%c.
Nhưng khi mình debug đoạn code sau trên trang vnoi thì có vẻ không giống với công thức:

long long power(long long a, long long b, long long c) {
    long long ans = 1;
    for(int i = 1; i <= b; i++) {
        ans *= a;
        ans %= c;
    }
    return ans;
 }

Ví dụ khi tính (5^2)%3 thì theo công thức mình sẽ được: ((5%3)*(5%3))%3.
Nhưng theo đoạn code trên thì sẽ được: ((5%3)*5)%3.
Vẫn cho ra kết quả đúng, nhưng mình không biết tại sao. Mong được các bác lí giải hộ.

rogp10 · January 4, 2019, 8:43am

Không có nhân b đâu bạn còn đoạn code kia cũng bình thường (brute force).

Lấy a = a % c trước là đủ.

hunghinh2000 · January 4, 2019, 8:56am

công thức đó mình lấy trên wiki mà bạn, công thức gốc có nhân b luôn mà

noname00 · January 4, 2019, 9:01am

Công thức của bạn sai rồi.

Đây là công thức tính (a * b) % c.

Theo công thức đồng dư

$5\equiv (5 \% 3)\ (mod\ 3)\\ \Rightarrow 5 * 5 \equiv 5 * (5 \% 3)\equiv (5 \% 3) * (5 \% 3)\ (mod\ 3)\\$

hay $5*5\equiv(5*5)\%3 \equiv (5\%3)*(5\%3)\ (mod\ 3)$

Tương tự với $a ^ b \equiv (a \% c)^b\ (mod\ c)$

hunghinh2000 · January 4, 2019, 9:02am

À ok cảm ơn bác, não mình đã được thông

rogp10 · January 25, 2019, 9:34am

Chắc là trang vnoi mà mình đọc lại thấy đâu có viết vậy.

Hiểu đơn giản là a*b % c = ((a%c) * b) % c.
Theo định nghĩa phép chia a = c*k + a%c với k là số nguyên.
Vậy a*b = (c*k + a%c)*b
mà c*k*b chia hết cho c nên phần còn lại là số dư.

Dùng đồng dư:

a = r (mod c) (đn là c | a - r)
<=> a*b = r*b (mod c) b!=0
=> a*b = (a%c)*b (mod c)