10.3K 778 121

Đã đăng vào thg 9 13, 2021 8:22 SA 10 phút đọc

17.5K

Phép nhân Ấn Độ - Thuật toán bình phương và nhân

Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu về hai kĩ thuật khá quen thuộc và có tính ứng dụng cao trong các bài toán số học, đó là Phép nhân Ấn Độ và Thuật toán bình phương và nhân - những kĩ thuật sẽ giúp các bạn tính toán $a \times n$ và $a^n$ trong thời gian $O\big(\log(n)\big)$ . Mặc dù nghe có vẻ khá vô dụng (bởi vì thực ra phép nhân chỉ cần thực hiện trực tiếp), nhưng đối với một số trường hợp thì chúng lại rất có ích (đặc biệt với ngôn ngữ C++).

Trước khi nghiên cứu chuyên đề này, các bạn cần phải có kiến thức về Giải thuật đệ quy, bởi vì các cài đặt đều sẽ sử dụng đệ quy. Nếu chưa nắm được thì các bạn hãy vào đọc về nó tại <i>đây</i>.

I. Phép nhân Ấn Độ

1. Đặt vấn đề

Xét một bài toán đơn giản như sau: Cho hai số $a, b \ (a, b \le 10^{18})$ . Tính giá trị biểu thức $(a\times b) \ \% \ 10^9$ .

Bài toán trên có thể dễ dàng giải quyết bằng tính chất phân phối của phép nhân đối với phép đồng dư thức: $(a\times b) \ \% \ 10^9=\big[(a \ \% \ 10^9)\times(b \ \% \ 10^9)\big] \ \% \ 10^9$ . Tuy nhiên, nếu như ta cần lấy số dư cho $10^{18}$ thì sao? Phép toán bằng tính chất phân phối bây giờ sẽ không thể thực hiện được, vì $\big[(a \ \% \ 10^{18})\times(b \ \% \ 10^{18})\big]\le 10^{36},$ dẫn đến kết quả của bước này sẽ bị vượt quá khả năng biểu diễn của kiểu số nguyên $64$ bit trong C++.

Phép nhân Ấn Độ sử dụng để tính $(a\times b) \ \% \ M$ trong trường hợp tính chất phân phối với phép đồng dư thức không thể áp dụng được vì lí do tràn số. Tuy nhiên điều này chỉ xảy ra với C++, còn đối với Python thì sẽ không ảnh hưởng gì cả.

2. Phép nhân Ấn Độ với đồng dư thức

Nguyên lí phép nhân Ấn Độ rất đơn giản như sau:

$(a \times b) = \begin{cases}a\times \frac{b}{2} + a\times \frac{b}{2},&\text{nếu }b\text{ là số chẵn }.\\ a\times \frac{b}{2} + a\times \frac{b}{2} + a,&\text{nếu }b\text{ là số lẻ}.\end{cases}$

Dựa trên lý thuyết này, ta sẽ kết hợp phép nhân Ấn Độ với tính chất phân phối của phép nhân, phép cộng với phép đồng dư thức để tính được $(a \times b) \ \% \ M,$ với $M \le 10^{18}$ mà không bị tràn số.

Lưu ý tính chất phân phối của phép cộng đối với phép đồng dư thức, tính chất này có thể áp dụng với cả phép nhân và phép trừ:

$(a + b) \ \% \ M = \big[(a \ \% \ M) + (b \ \% \ M)\big] \ \% \ M$

Cài đặt

Ngôn ngữ C++:

// Tính a * b % M
long long multiply_modulo(long long a, long long b, long long M)
{
    if (b == 0)
        return 0;

    long long t = multiply_modulo(a, b / 2, M) % M;

    if (b & 1)
        return ((t + t) % M + a % M) % M;
    else
        return (t + t) % M;
}

Ngôn ngữ Python:

# Tính a * b % M
def multiply_modulo(a, b, M):
    if b == 0:
        return 0
		
    t = multiply_modulo(a, b // 2, M)
    
    if b & 1:
        return ((t + t) % M + a % M) % M
    else:
        return (t + t) % M

Đánh giá độ phức tạp

Trong thuật toán, $b$ liên tục giảm đi một nửa, nên độ phức tạp của giải thuật là $O(\log_2(b))$ .

I. Thuật toán bình phương và nhân

1. Giải thuật chia để trị

Thông thường, để tính lũy thừa $a^b,$ ta sẽ cần sử dụng $b$ phép nhân liên tiếp trong một vòng lặp. Nếu như $b$ là một số lớn cỡ $10^9$ trở lên, thì việc tính toán sẽ mất rất nhiều thời gian, không thể đáp ứng được yêu cầu trong các bài toán lập trình. Mặt khác, kết quả của phép lũy thừa thường rất lớn, nên đề bài sẽ yêu cầu thí sinh in ra kết quả sau khi chia lấy dư cho một giá trị $M$ nào đó.

Dựa trên tư tưởng phép nhân Ấn Độ, ta có thể điều chỉnh công thức một chút để tính được lũy thừa $a^b \ \%M,$ với $a, b, M \le 10^9$ . Công thức đơn giản như sau:

$(a \times b) = \begin{cases}a^{\frac{b}{2}} \times a^{\frac{b}{2}},&\text{nếu }b\text{ là số chẵn }.\\ a^{\frac{b}{2}} \times a^{\frac{b}{2}} \times a,&\text{nếu }b\text{ là số lẻ}.\end{cases}$

Cài đặt

Trong cài đặt dưới đây, tác giả sẽ cài đặt mẫu cả phiên bản đệ quy và phiên bản khử đệ quy của thuật toán.

Ngôn ngữ C++:

// Tính a^b mod M.
long long power_modulo(long long a, long long b, long long M) 
{
    if (b == 0)
        return 1LL;

    long long half = power_modulo(a, b / 2, M) % M;

    if (b & 1)
        return (((half * half) % M) * (a % M)) % M;
    else
        return (half * half) % M;
}

Ngôn ngữ Python:

# Tính a^b % M
def power_modulo(a, b, M):
    if b == 0:
        return 1
    
    half = power_modulo(a, b // 2, M) % M

    if b & 1:
        return (half * half * a) % M
    else:
        return (half * half) % M

Ngoài ra, ta cũng có thể cài đặt giải thuật bằng phương pháp khử đệ quy để đẩy nhanh tốc độ thuật toán hơn một chút:

Ngôn ngữ C++:

// Tính a^b % M khử đệ quy.
long long power_modulo_non_recur(long long a, long long b, long long M)
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % M;
			
        a = (a * a) % M;
        b /= 2;
    }
	
    return res;
}

Ngôn ngữ Python:

def power_modulo_non_recur(a, b, M):
    res = 1
    while b != 0:
        if b % 1:
            res = (res * a) % M
			
        a = (a * a) % M
        b = b // 2
		
    return res

Đánh giá độ phức tạp

Trong thuật toán, $b$ liên tục giảm đi một nửa, nên độ phức tạp của giải thuật là $O\big(\log_2(b)\big)$ . Mặc dù độ phức tạp của cả hai cách cài đặt là tương tự nhau, nhưng trong thực tế cách làm khử đệ quy sẽ chạy nhanh hơn một chút do không phải gọi đệ quy.

2. Tính $a^b\text{ }\%\text{ }M$ với $M \le 10^{18}$

Trong trường hợp $M \le 10^{18}$ , dựa trên những gì đã phân tích ở phần I, phép nhân thông thường sẽ không thể áp dụng trong C++ vì lí do xảy ra tràn số. Vì vậy, ta sẽ kết hợp thêm phép nhân Ấn Độ trong trường hợp này. Độ phức tạp sẽ trở thành $O(\log_2(b)^2)$

Cài đặt

Ngôn ngữ C+++:

long long power_modulo(long long a, long long b, long long M)  
{
    if (b == 0)
        return 1LL;

    long long half = power_modulo(a, b / 2LL, M) % M;
    half = multiply_modulo(half, half, M);

    if (b & 1)
        return multiply_modulo(half, a, M);
    else
        return half;
}

Ngôn ngữ Python:

Mặc dù phép nhân trong Python không bị tràn số, tuy nhiên bản chất ngôn ngữ này vẫn sẽ phải sử dụng các thuật toán xử lý số nguyên lớn để thao tác khi dữ liệu quá to, nên có khả năng chương trình sẽ bị chạy quá thời gian. Vì vậy, tác giả vẫn đưa vào đoạn code bằng Python để các bạn sử dụng khi cần thiết:

def power_modulo(a, b, M):  
{
    if b == 0:
        return 1;

    half = power_modulo(a, b // 2, M) % M;
    half = multiply_modulo(half, half, M);

    if (b & 1)
        return multiply_modulo(half, a, M);
    else
        return half;
}

Đánh giá độ phức tạp

Do sử dụng kết hợp cả thuật toán bình phương và nhân lẫn phép nhân Ấn Độ, nên độ phức tạp tổng quát sẽ là $O(\log^2 b)$ .

3. Tính $a^b \ \% \ M$ trong trường hợp $b$ là số lớn và $M$ là số nguyên tố

Đối với các trường hợp $b$ là số lớn - hiểu là các số nằm ngoài khả năng lưu trữ của kiểu số trong C++ và phải lưu bằng kiểu chuỗi - khi đó giải thuật tính $a^b \ \% \ M$ sẽ trở nên hơi phức tạp nếu như chúng ta cài đặt bằng các phép toán số lớn. Tuy nhiên, trong trường hợp $M$ là một số nguyên tố, dựa vào một số tính chất số học, ta có thể thu gọn được việc tính toán như sau:

Thứ nhất, cần biết định lý nhỏ Fermat được phát biểu như sau: Nếu $M$ là một số nguyên tố thì:

$a^{M-1} \equiv 1 \ (\text{mod } M), \text{với } a \ \% \ M \ne 0$
Lại có: $a^b \ \% \ M = (a^{M-1}.a^{M-1}...a^{M-1}.a^x) \ \% \ M,$ với $a^{M-1}$ lặp lại $\left \lfloor{\frac{b}{M-1}} \right \rfloor$ lần và $x = b \ \% \ (M-1)$ . Từ đây suy ra:

$a^b \ \% \ M = (1.1.1...1.a^x) \ \% \ M = a^x \ \% \ M$

Tới đây chúng ta có thể áp dụng thuật toán bình phương và nhân một cách bình thường mà không sợ bị tràn số. Tất nhiên vẫn sẽ cần lưu ý về giới hạn của $M$ để lựa chọn phép nhân thông thường hay phép nhân Ấn Độ.

Việc cài đặt xin dành lại cho bạn đọc.

III. Một số bài toán minh họa

1. Chữ số tận cùng

Đề bài

Cho hai số nguyên $a$ và $b$ . Cần tìm chữ số tận cùng của $a^b?$

Input:

Một dòng duy nhất chứa hai số nguyên $a$ và $b$ .

Ràng buộc:

$1 \le a, b \le 10^9$ .

Output:

Đưa ra chữ số tận cùng của $a^b$ .

Sample Input:

3 10

Sample Output:

Ý tưởng

Để lấy chữ số tận cùng của một số nguyên dương $n,$ ta lấy $n$ chia cho $10$ và kết quả là số dư của phép chia.

Áp dụng công thức trên, ta có kết quả bài toán là $a^b \ \% \ 10$ .

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

void enter(long long &a, long long &b)
{
    cin >> a >> b;
}

long long power_modulo(long long a, long long b, long long mod)
{
    if (b == 0)
        return 1LL;

    long long half = power_modulo(a, b / 2, mod) % mod;

    if (b & 1)
        return (((half * half) % mod) * (a % mod)) % mod;
    else
        return (half * half) % mod;
}

main()
{
    long long a, b;

    enter(a, b);
    cout << power_modulo(a, b, 10);

    return 0;
}

Ngôn ngữ Python:

def power_modulo(a, b, mod):
    if b == 0:
        return 1
    
    half = power_modulo(a, b // 2, mod) % mod

    if b & 1:
        return (half * half * a) % mod
    else:
        return (half * half) % mod


if __name__ == '__main__':
    a = int(input())
    b = int(input())

    print(power_modulo(a, b, 10))

2. Đỗ xe

Đề bài

Một bãi đỗ xe có $2n - 2$ chỗ đỗ xe liên tiếp, và các CEO của bãi đỗ xe dự định lấp đầy bãi đỗ xe bằng $4$ loại xe ở $4$ màu khác nhau để làm lễ khai trương. Khi nhìn những chiếc xe xếp thành một đường thẳng, họ thấy rằng nếu như sắp xếp lại các xe sao cho có ít nhất một đoạn gồm đúng $n$ chiếc xe cùng màu đứng cạnh nhau, thì bãi đỗ xe sẽ đẹp hơn.

Hãy giúp các CEO đếm xem có bao nhiêu cách sắp xếp như vậy? Biết rằng số lượng xe của mỗi loại đều lớn hơn số lượng chỗ đỗ xe.

Input:

Chứa duy nhất số nguyên dương $n$ .

Ràng buộc:

$2 \le n \le 10^9$ .

Output:

In ra số nguyên duy nhất là số lượng cách sắp xếp những chiếc xe vào $2n - 2$ chỗ đỗ xe theo yêu cầu. Do kết quả có thể rất lớn, chỉ cần in ra số dư của nó sau khi chia cho $10^9 + 7$ .

Sample Input:

Sample Output:

Ý tưởng

Ta phải chọn ra tổng cộng $2n - 2$ chiếc xe từ $4$ loại xe khác nhau để đặt trên một đường thẳng, sao cho có chính xác $n$ chiếc xe cùng màu đứng liên tiếp nhau. Những phương án chọn có thể là: Đặt $n$ chiếc cùng màu ở $n$ vị trí liên tiếp ở đầu đường thẳng, hoặc đặt ở $n$ vị trí liên tiếp ở cuối đường thẳng, hoặc đặt ở $n$ vị trí liên tiếp ở giữa đường thẳng.

Nếu như $n$ chiếc cùng màu được đặt ở $n$ vị trí đầu tiên hoặc $n$ vị trí cuối cùng, thì có $4$ cách để chọn màu cho $n$ chiếc đó, và $3$ cách để chọn ra một chiếc xe khác màu đặt bên cạnh $n$ chiếc đó. Còn lại $2n - 2 - (n + 1) = n - 3$ vị trí ở giữa, ta có thể chọn một trong $4$ màu cho mỗi vị trí. Vậy tổng số cách chọn trong trường hợp này là $2 \times 4 \times 3 \times 4^{n - 3}$ (vì có thể đặt $n$ chiếc vào đầu hoặc cuối đường thẳng).

Nếu như $n$ chiếc cùng màu được đặt ở vị trí giữa đường thẳng, thì vẫn có $4$ cách chọn màu cho $n$ chiếc này, và có thêm $3$ cách chọn màu khác với màu đó cho mỗi chiếc kề trái kề phải của $n$ chiếc đó. Còn $n - 4$ chiếc còn lại, mỗi chiếc có khả năng chọn $4$ màu. Vậy tổng số cách chọn cho một đoạn gồm $n$ chiếc cùng màu là $4 \times 3^2 \times 4^{n - 4}$ . Ngoài ra lại có $n - 3$ vị trí để đặt $n$ chiếc cùng màu vào giữa đoạn, nên tổng số cách chọn trong trường hợp này là: $(n - 3) \times 4 \times 3^2 \times 4^{n - 4}$ .

Vậy kết quả cuối cùng là: $2 \times 4 \times 3 \times 4^{n - 3} + (n - 3) \times 4 \times 3^2 \times 4^{n - 4}$ . Vì kết quả phải chia dư cho $10^9 + 7$ nên ta sẽ áp dụng giải thuật bình phương và nhân với đồng dư thức.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;

long long power_modulo(long long a, long long b, long long mod)
{
    if (b == 0)
        return 1LL;

    long long half = power_modulo(a, b / 2, mod) % mod;

    if (b & 1)
        return (((half * half) % mod) * (a % mod)) % mod;
    else
        return (half * half) % mod;
}

main()
{
    int n;
    cin >> n;

    long long x = (24 * power_modulo(4, n - 3, mod)) % mod;
    long long y = ((((n - 3) * 36) % mod) * power_modulo(4, n - 4, mod)) % mod;

    cout << (x + y) % mod;
}

Ngôn ngữ Python:

def power_modulo(a, b, mod):
    if b == 0:
        return 1
    
    half = power_modulo(a, b // 2, mod) % mod

    if b & 1:
        return (half * half * a) % mod
    else:
        return (half * half) % mod


if __name__ == '__main__':
    n = int(input())

    mod = int(1000000007)
    x = (24 * power_modulo(4, n - 3, mod)) % mod
    y = ((((n - 3) * 36) % mod) * power_modulo(4, n - 4, mod)) % mod

    print((x + y) % mod)

IV. Tài liệu tham khảo

I. Phép nhân Ấn Độ

1. Đặt vấn đề

2. Phép nhân Ấn Độ với đồng dư thức

Cài đặt

Đánh giá độ phức tạp

I. Thuật toán bình phương và nhân

1. Giải thuật chia để trị

Cài đặt

Đánh giá độ phức tạp

2. Tính ab % Ma^b\text{ }\%\text{ }Mab % M với M≤1018M \le 10^{18}M≤1018

Cài đặt

Đánh giá độ phức tạp

3. Tính ab % Ma^b \ \% \ Mab % M trong trường hợp bbb là số lớn và MMM là số nguyên tố

III. Một số bài toán minh họa

1. Chữ số tận cùng

Đề bài

Ý tưởng

Cài đặt

2. Đỗ xe

Đề bài

Ý tưởng

Cài đặt

IV. Tài liệu tham khảo

Mục lục

2. Tính $a^b\text{ }\%\text{ }M$ với $M \le 10^{18}$

3. Tính $a^b \ \% \ M$ trong trường hợp $b$ là số lớn và $M$ là số nguyên tố