+13

Phép nhân Ấn Độ - Thuật toán bình phương và nhân

Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu về hai kĩ thuật khá quen thuộc và có tính ứng dụng cao trong các bài toán số học, đó là Phép nhân Ấn Độ và Thuật toán bình phương và nhân - những kĩ thuật sẽ giúp các bạn tính toán a×na \times n và ana^n trong thời gian O(log(n))O\big(\log(n)\big). Mặc dù nghe có vẻ khá vô dụng (bởi vì thực ra phép nhân chỉ cần thực hiện trực tiếp), nhưng đối với một số trường hợp thì chúng lại rất có ích (đặc biệt với ngôn ngữ C++).

Trước khi nghiên cứu chuyên đề này, các bạn cần phải có kiến thức về Giải thuật đệ quy, bởi vì các cài đặt đều sẽ sử dụng đệ quy. Nếu chưa nắm được thì các bạn hãy vào đọc về nó tạ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,b1018)a, b \ (a, b \le 10^{18}). Tính giá trị biểu thức (a×b) % 109(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×b) % 109=[(a % 109)×(b % 109)] % 109(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 101810^{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ì [(a % 1018)×(b % 1018)]1036,\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 6464 bit trong C++.

Phép nhân Ấn Độ sử dụng để tính (a×b) % M(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 này chỉ xảy ra với C++, còn đối với Python thì sẽ không ảnh hưởng gì cả.

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×b)={a×b2+a×b2,neˆˊb laˋ soˆˊ cha˘˜.a×b2+a×b2+a,neˆˊb laˋ soˆˊ lẻ.(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×b) % M,(a \times b) \ \% \ M, với M1018M \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=[(a % M)+(b % M)] % M(a + b) \ \% \ M = \big[(a \ \% \ M) + (b \ \% \ M)\big] \ \% \ M

Cà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, bb 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(log2(b))O(\log_2(b)).

I. Thuật toán bình phương và nhân

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

Thông thường, để tính lũy thừa ab,a^b, ta sẽ cần sử dụng bb phép nhân liên tiếp trong một vòng lặp. Nếu như bb là một số lớn cỡ 10910^9 trở lên, thì việc tính toán sẽ mất rất nhiều thời gian, không thể đáp ứng được yêu cầu trong các bài toán lập trình. Mặt khác, kết quả của phép lũy thừa thường rất lớn, nên đề bài sẽ yêu cầu thí sinh in ra kết quả sau khi chia lấy dư cho một giá trị MM nà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 ab %M,a^b \ \%M, với a,b,M109a, b, M \le 10^9. Công thức đơn giản như sau:

(a×b)={ab2×ab2,neˆˊb laˋ soˆˊ cha˘˜.ab2×ab2×a,neˆˊb laˋ soˆˊ lẻ.(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++:

// Tí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, bb 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(log2(b))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 ab % Ma^b\text{ }\%\text{ }M với M1018M \le 10^{18}

Trong trường hợp M1018M \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 sẽ 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(log2(b)2)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ù phép nhân trong Python không bị trà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(log2b)O(\log^2 b).

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

Đối với các trường hợp bb 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 ab % Ma^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 MM 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 MM là một số nguyên tố thì:

    aM11 (mod M),với a % M0a^{M-1} \equiv 1 \ (\text{mod } M), \text{với } a \ \% \ M \ne 0

  • Lại có: ab % M=(aM1.aM1...aM1.ax) % M,a^b \ \% \ M = (a^{M-1}.a^{M-1}...a^{M-1}.a^x) \ \% \ M, với aM1a^{M-1} lặp lại bM1\left \lfloor{\frac{b}{M-1}} \right \rfloor lần và x=b % (M1)x = b \ \% \ (M-1). Từ đây suy ra:

    ab % M=(1.1.1...1.ax) % M=ax % Ma^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 toán bình phương và 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 MM để 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ố bài toán minh họa

1. Chữ số tận cùng

Đề bài

Cho hai số nguyên aa và bb. Cần tìm chữ số tận cùng của ab?a^b?

Input:

  • Một dòng duy nhất chứa hai số nguyên aa và bb.

Ràng buộc:

  • 1a,b1091 \le a, b \le 10^9.

Output:

  • Đưa ra chữ số tận cùng của aba^b.

Sample Input:

3 10

Sample Output:

9

Ý tưởng

Để lấy chữ số tận cùng của một số nguyên dương n,n, ta lấy nn chia cho 1010 và kết quả là số dư của phép chia.

Áp dụng công thức trên, ta có kết quả bài toán là ab % 10a^b \ \% \ 10.

Cà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

Đề bài

Một bãi đỗ xe có 2n22n - 2 chỗ đỗ xe liên tiếp, và các CEO của bãi đỗ xe dự định lấp đầy bãi đỗ xe bằng 44 loại xe ở 44 màu khác nhau để làm lễ khai trương. Khi nhìn những chiếc xe xếp thành một đường thẳng, họ thấy rằng nếu như sắp xếp lại các xe sao cho có ít nhất một đoạn gồm đúng nn chiếc xe cùng màu đứng cạnh nhau, thì bãi đỗ xe sẽ đẹp hơn.

Hãy giúp các CEO đếm xem có bao nhiêu cách sắp xếp như vậy? Biết rằng số lượng xe của mỗi loại đều lớn hơn số lượng chỗ đỗ xe.

Input:

  • Chứa duy nhất số nguyên dương nn.

Ràng buộc:

  • 2n1092 \le n \le 10^9.

Output:

  • In ra số nguyên duy nhất là số lượng cách sắp xếp những chiếc xe vào 2n22n - 2 chỗ đỗ xe theo yêu cầu. Do kết quả có thể rất lớn, chỉ cần in ra số dư của nó sau khi chia cho 109+710^9 + 7.

Sample Input:

3

Sample Output:

24

Ý tưởng

Ta phải chọn ra tổng cộng 2n22n - 2 chiếc xe từ 44 loại xe khác nhau để đặt trên một đường thẳng, sao cho có chính xác nn chiếc xe cùng màu đứng liên tiếp nhau. Những phương án chọn có thể là: Đặt nn chiếc cùng màu ở nn vị trí liên tiếp ở đầu đường thẳng, hoặc đặt ở nn vị trí liên tiếp ở cuối đường thẳng, hoặc đặt ở nn vị trí liên tiếp ở giữa đường thẳng.

Nếu như nn chiếc cùng màu được đặt ở nn vị trí đầu tiên hoặc nn vị trí cuối cùng, thì có 44 cách để chọn màu cho nn chiếc đó, và 33 cách để chọn ra một chiếc xe khác màu đặt bên cạnh nn chiếc đó. Còn lại 2n2(n+1)=n32n - 2 - (n + 1) = n - 3 vị trí ở giữa, ta có thể chọn một trong 44 màu cho mỗi vị trí. Vậy tổng số cách chọn trong trường hợp này là 2×4×3×4n32 \times 4 \times 3 \times 4^{n - 3} (vì có thể đặt nn chiếc vào đầu hoặc cuối đường thẳng).

Nếu như nn chiếc cùng màu được đặt ở vị trí giữa đường thẳng, thì vẫn có 44 cách chọn màu cho nn chiếc này, và có thêm 33 cách chọn màu khác với màu đó cho mỗi chiếc kề trái kề phải của nn chiếc đó. Còn n4n - 4 chiếc còn lại, mỗi chiếc có khả năng chọn 44 màu. Vậy tổng số cách chọn cho một đoạn gồm nn chiếc cùng màu là 4×32×4n44 \times 3^2 \times 4^{n - 4}. Ngoài ra lại có n3n - 3 vị trí để đặt nn chiếc cùng màu vào giữa đoạn, nên tổng số cách chọn trong trường hợp này là: (n3)×4×32×4n4(n - 3) \times 4 \times 3^2 \times 4^{n - 4}.

Vậy kết quả cuối cùng là: 2×4×3×4n3+(n3)×4×32×4n42 \times 4 \times 3 \times 4^{n - 3} + (n - 3) \times 4 \times 3^2 \times 4^{n - 4}. Vì kết quả phải chia dư cho 109+710^9 + 7 nên ta sẽ áp dụng giải thuật bình phương và nhân với đồng dư thức.

Cà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


©️ Tác giả: Vũ Quế Lâm từ Viblo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.