Tính a*b theo lũy thừa nhị phân

Như ta đã biết với a và b là 2 số nguyên 

•         a*b = a*(b-1)+a  khi b>0

cách làm này cũng vẫn sẽ mất  b bước thực hiện. Tượng tự ta có tính chất sau trong phép nhân

•         a*b=a*(b/2)+a*(b/2)

Từ đó: ta có thể phân tích a*b như sau:

• a*b = a*(b/2)+a*(b/2)               khi b chẵn
• a*b= a*(b/2) + a*(b/2)+a          khi b lẻ

Với tính chất này tương tự như lũy thừa ta có thể tính a*b bằng cách tính a*(b/2) mà khong cần tính 

a*(b-1)+a... từ đó ta có tính a*b với độ phức tạp là O(log(n))

int bin_multiplication(int a, int b)

{

    int res = 0;

    while (b > 0) {

        if (b % 2 == 1)

            res = res + a;

        a= a + a;

        b = b >> 1; // b=b/2

    }

    return res;

}

- Đối với cách làm này ta không chỉ tính toán a*b với độ phức tạp là O(log(n)) mà ta có thể thông qua cách làm này để xử lý khi lấy 2 số lớn nhân nhau và mod cho một số m

-Ắt hản chúng ta đã từng gặp một số bài toán yêu cầu modulo đáp án cho một số m thông thường m = 1e9+7.

-VD cụ thể ta có bài toán (a*b)%m với :

• a=1e13+3
• b=1e12+7
• m = 1e9+7

-Nếu ta lấy trực tiếp (a*b)%m thì kết quả sẽ lập tức bị tràn khỏi kiểu dữ liệu int hay thậm chí là kiểu dữ liệu long long. Tất nhiên vẫn sẽ có thể sử dụng công thức mod

•    (a*b)%m = (a%m*b%m)%m

-Điều này sẽ làm giảm kích thước a và b trước khi nhân để a và b có thể nhân nhau mà không vượt ngoại phạm vi kiểu dữ liệu long long trước khi mod

-Tuy nhiên trong một số bài toán số m có thể đạt tới 1e18 vì lẻ đó nếu ta áp dụng công thức trên thì 

• a%m  vẫn sẽ bằng 1e13+3
• b%m  vẫn sẽ bằng 1e12+7
• với m = 1e18

-Kết quả vẫn sẽ chăng thay đổi gì vì a và b đều bé hơn số m nên khi (a*b)%m vẫn sẽ bị tràn số

-Khi đó ta sẽ áp dụng kỹ thuật tính a*b theo lũy thừa nhị phân (bin_multiplication)

long long  bin_multiplication(long long  a, long long  b, long long m)

{

    long long  res = 0;

    while (b > 0) {

        if (b % 2 == 1)

            res = res + a;

            res = res % m;

        a= a + a;

        a= a % m ;

        b = b >> 1; // b=b/2

    }

    return res;

}

- Với cách làm này ta vẫn sẽ đảm bảo (a*b) %m sẽ không bị tràn số khi m đạt tới 1e18 mà vẫn đảm bảo độ phức tạp thuật toán trong thời gian cho phép đủ dư giả để giải quyết các bài toán yêu cầu 1s