Khóa học CTDL và GT

Bài 5.1: Nguyên lý đệ quy và điều kiện dừng,

Chào mừng trở lại với hành trình khám phá thế giới Cấu trúc dữ liệu và Giải thuật! Sau những bài học về cấu trúc dữ liệu cơ bản, đã đến lúc chúng ta chạm tay vào một trong những kỹ thuật giải quyết vấn đề mạnh mẽ và thanh lịch nhất trong lập trình: Đệ quy (Recursion).

Đệ quy không chỉ là một khái niệm, nó là một cách suy nghĩ về bài toán. Nó cho phép chúng ta giải quyết những vấn đề phức tạp bằng cách chia nhỏ chúng thành những phiên bản đơn giản hơn của chính nó, cho đến khi đạt được một trường hợp đủ đơn giản để giải quyết trực tiếp. Nghe có vẻ hơi giống "vòng lặp" phải không? Nhưng sự khác biệt nằm ở cách tiếp cận vấn đề và, quan trọng nhất, ở Nguyên lý Đệ quy và Điều kiện dừng.

Đệ quy là gì? Suy nghĩ theo kiểu "Gương trong Gương"

Hãy tưởng tượng bạn đứng giữa hai tấm gương đặt song song. Bạn sẽ nhìn thấy hình ảnh phản chiếu của chính mình lặp đi lặp lại vô hạn lần. Đó là một hình ảnh trực quan khá tốt về ý tưởng đệ quy, nhưng trong lập trình, chúng ta cần một cách để dừng chuỗi lặp lại đó.

Về mặt kỹ thuật, đệ quy là một kỹ thuật lập trình trong đó một hàm tự gọi chính nó trong định nghĩa của nó.

Mục tiêu của việc một hàm tự gọi mình là để giải quyết một phiên bản nhỏ hơn hoặc đơn giản hơn của bài toán ban đầu. Quá trình này cứ tiếp tục cho đến khi bài toán trở nên đủ nhỏ và đơn giản để có thể giải quyết trực tiếp mà không cần gọi đệ quy thêm nữa.

Tầm quan trọng Tối quan trọng của Điều kiện dừng (Base Case)

Quay lại ví dụ hai tấm gương. Nếu không có gì thay đổi, hình ảnh sẽ lặp lại vô hạn. Trong lập trình, điều này tương đương với đệ quy vô hạn (infinite recursion), và kết quả là chương trình của bạn sẽ gặp lỗi Stack Overflow (ngăn xếp tràn) vì hệ thống không còn đủ bộ nhớ để lưu trữ các lời gọi hàm đệ quy liên tiếp.

Đây chính là lúc Điều kiện dừng (Base Case) xuất hiện.

Điều kiện dừng là trường hợp đơn giản nhất của bài toán mà chúng ta có thể giải quyết ngay lập tức, mà không cần gọi đệ quy thêm nữa. Nó là "phao cứu sinh" giúp chuỗi gọi đệ quy dừng lại.

Một lời gọi đệ quy hợp lệ luôn luôn phải có:

1. Trường hợp đệ quy (Recursive Case): Trường hợp bài toán lớn hơn, nơi hàm tự gọi chính nó để giải quyết một hoặc nhiều phiên bản nhỏ hơn của bài toán. Quan trọng là mỗi lần gọi đệ quy, bài toán phải tiến gần hơn đến điều kiện dừng.
2. Điều kiện dừng (Base Case): Trường hợp bài toán đủ đơn giản để giải quyết trực tiếp, không cần gọi đệ quy. Đây là nơi chuỗi gọi hàm kết thúc.

Nếu thiếu điều kiện dừng hoặc trường hợp đệ quy không tiến tới điều kiện dừng, bạn sẽ gặp lỗi đệ quy vô hạn.

Đệ quy hoạt động như thế nào (Ẩn sau)? Ngăn xếp gọi hàm (Call Stack)

Khi một hàm được gọi, hệ thống sẽ lưu trữ thông tin về lời gọi đó (như các biến cục bộ, địa chỉ trả về...) vào một cấu trúc dữ liệu gọi là Ngăn xếp gọi hàm (Call Stack).

Khi một hàm đệ quy gọi chính nó, một khung ngăn xếp (stack frame) mới lại được tạo cho lời gọi mới, và quá trình này lặp lại. Chỉ khi lời gọi đệ quy đạt đến điều kiện dừng, hàm sẽ thực hiện hành động của nó (giải quyết trường hợp đơn giản nhất) và trả về kết quả. Khi kết quả được trả về, khung ngăn xếp của lời gọi đó sẽ bị hủy bỏ. Kết quả này sau đó được sử dụng bởi lời gọi hàm ở tầng trên (lời gọi cha) để tiếp tục tính toán. Quá trình trả về này diễn ra liên tục cho đến khi lời gọi hàm ban đầu kết thúc.

Hiểu biết về Stack giúp ta hình dung được cách các lời gọi đệ quy được quản lý và cách kết quả được truyền ngược trở lên.

Các ví dụ minh họa bằng C++

Để làm cho khái niệm này trở nên rõ ràng hơn, chúng ta hãy xem xét một vài ví dụ kinh điển về đệ quy trong C++.

Ví dụ 1: Tính Giai thừa (Factorial)

Giai thừa của một số nguyên không âm n, ký hiệu là n!, là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n.

• 5! = 5 * 4 * 3 * 2 * 1 = 120
• 3! = 3 * 2 * 1 = 6

Theo định nghĩa toán học, chúng ta có thể viết:

• n! = n * (n-1)! cho n > 0
• 0! = 1 (định nghĩa)

Đây chính là cấu trúc đệ quy!

• Trường hợp đệ quy: n! = n * (n-1)! - Tính giai thừa của n dựa trên giai thừa của n-1. n-1 rõ ràng nhỏ hơn n, tiến gần hơn đến 0.
• Điều kiện dừng: 0! = 1 - Khi n bằng 0, chúng ta biết ngay kết quả là 1 mà không cần tính giai thừa của số âm.

Bây giờ, hãy chuyển nó thành code C++:

#include <iostream>

// Hàm tính giai thừa sử dụng đệ quy
long long factorial(int n) {
    // 1. Điều kiện dừng (Base Case)
    // Nếu n là 0 hoặc 1, giai thừa là 1. Đây là trường hợp đơn giản nhất.
    if (n == 0 || n == 1) {
        return 1;
    }
    // Trường hợp này cũng có thể coi là điều kiện dừng để đơn giản code.
    // if (n == 0) return 1;
    // if (n == 1) return 1;


    // 2. Trường hợp đệ quy (Recursive Case)
    // Nếu n lớn hơn 1, giai thừa của n bằng n nhân với giai thừa của (n-1).
    // Lời gọi factorial(n-1) là lời gọi đệ quy, giải quyết bài toán nhỏ hơn.
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    std::cout << "Giai thua cua " << num << " la: " << factorial(num) << std::endl; // Output: 120

    num = 0;
    std::cout << "Giai thua cua " << num << " la: " << factorial(num) << std::endl; // Output: 1

    num = 1;
    std::cout << "Giai thua cua " << num << " la: " << factorial(num) << std::endl; // Output: 1

    // Lưu ý: Đệ quy cho số âm sẽ gây ra lỗi Stack Overflow vì không có điều kiện dừng cho số âm.
    // num = -5;
    // std::cout << "Giai thua cua " << num << " la: " << factorial(num) << std::endl; // Lỗi!

    return 0;
}

Giải thích Code:

• Hàm factorial(int n) nhận một số nguyên n.
• Đầu tiên, nó kiểm tra if (n == 0 || n == 1). Đây chính là điều kiện dừng (base case). Nếu n là 0 hoặc 1, hàm trả về 1 ngay lập tức mà không gọi đệ quy.
• Nếu n lớn hơn 1, chương trình thực hiện khối else. Dòng return n * factorial(n - 1); là trường hợp đệ quy (recursive case). Hàm factorial tự gọi chính nó với đối số n - 1. Kết quả của lời gọi đệ quy này sẽ được nhân với n hiện tại trước khi trả về.
• Quá trình này tiếp diễn cho đến khi đối số truyền vào lời gọi đệ quy là 1 hoặc 0, kích hoạt điều kiện dừng. Sau đó, các kết quả sẽ được "cuộn" ngược lên ngăn xếp, tính toán và trả về cho đến khi lời gọi ban đầu hoàn thành.

Ví dụ: factorial(4) -> 4 * factorial(3) -> 4 * (3 * factorial(2)) -> 4 * (3 * (2 * factorial(1))) -> 4 * (3 * (2 * 1)) -> 4 * (3 * 2) -> 4 * 6 -> 24.

Ví dụ 2: Dãy Fibonacci

Dãy Fibonacci là một dãy số bắt đầu bằng 0 và 1, trong đó mỗi số tiếp theo là tổng của hai số đứng trước nó. 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Định nghĩa toán học:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) cho n > 1

Lại là cấu trúc đệ quy rõ ràng!

• Trường hợp đệ quy: F(n) = F(n-1) + F(n-2) - Tính số Fibonacci thứ n dựa trên hai số Fibonacci đứng trước nó. n-1 và n-2 nhỏ hơn n, tiến gần hơn đến 0 và 1.
• Điều kiện dừng: F(0) = 0 và F(1) = 1 - Khi n bằng 0 hoặc 1, chúng ta biết ngay kết quả mà không cần gọi đệ quy thêm. Có hai điều kiện dừng ở đây.

Code C++:

#include <iostream>

// Hàm tính số Fibonacci thứ n sử dụng đệ quy
int fibonacci(int n) {
    // 1. Điều kiện dừng (Base Cases)
    // Trường hợp n là 0 hoặc 1 là trường hợp đơn giản nhất.
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    // 2. Trường hợp đệ quy (Recursive Case)
    // Nếu n lớn hơn 1, số Fibonacci thứ n bằng tổng của hai số đứng trước nó.
    // Có hai lời gọi đệ quy ở đây: fibonacci(n-1) và fibonacci(n-2).
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int num = 7;
    std::cout << "So Fibonacci thu " << num << " la: " << fibonacci(num) << std::endl; // Output: 13 (Day: 0, 1, 1, 2, 3, 5, 8, 13)

    num = 0;
    std::cout << "So Fibonacci thu " << num << " la: " << fibonacci(num) << std::endl; // Output: 0

    num = 1;
    std::cout << "So Fibonacci thu " << num << " la: " << fibonacci(num) << std::endl; // Output: 1

    // Lưu ý: Phương pháp đệ quy trực tiếp này rất không hiệu quả với n lớn do tính toán lặp lại.
    // Hãy thử với n = 40 hoặc 45 và xem chương trình chạy chậm thế nào!
    // num = 40;
    // std::cout << "So Fibonacci thu " << num << " la: " << fibonacci(num) << std::endl; // Se rat cham!

    return 0;
}

Giải thích Code:

• Hàm fibonacci(int n) nhận một số nguyên n.
• Nó có hai điều kiện dừng: if (n == 0) return 0; và if (n == 1) return 1;. Đây là hai trường hợp cơ bản của dãy Fibonacci.
• Nếu n lớn hơn 1, hàm thực hiện trường hợp đệ quy: return fibonacci(n - 1) + fibonacci(n - 2);. Hàm tự gọi nó hai lần với đối số nhỏ hơn (n-1 và n-2), sau đó cộng kết quả của hai lời gọi này lại.
• Lưu ý về hiệu suất: Mặc dù code rất thanh lịch và bám sát định nghĩa toán học, phương pháp đệ quy trực tiếp này không hiệu quả cho các giá trị n lớn. Lý do là các giá trị Fibonacci trung gian (như fibonacci(3) khi tính fibonacci(5)) bị tính toán nhiều lần trong các nhánh đệ quy khác nhau. Đây là một nhược điểm cần cân nhắc khi sử dụng đệ quy.

Ví dụ 3: Tính tổng các phần tử trong Vector/Mảng

Chúng ta có thể sử dụng đệ quy để tính tổng các phần tử trong một vector (hoặc mảng) các số nguyên.

Ý tưởng:

• Tổng của một vector là phần tử đầu tiên cộng với tổng của phần còn lại của vector.

• Tổng của một vector rỗng là 0.

• Trường hợp đệ quy: sum(vec) = vec[0] + sum(vec[1...end]) - Tính tổng dựa trên phần tử đầu tiên và tổng của phần còn lại. Phần còn lại nhỏ hơn vector ban đầu.

• Điều kiện dừng: sum({}) = 0 - Tổng của vector rỗng.

Để triển khai trong C++, chúng ta có thể truyền vector và chỉ số bắt đầu để chỉ ra phần "còn lại" của vector.

#include <iostream>
#include <vector>
#include <numeric> // Chỉ để so sánh với std::accumulate

// Hàm tính tổng các phần tử trong vector sử dụng đệ quy
// Tham số: vector<int>& vec - vector cần tính tổng (truyền tham chiếu để tránh sao chép lớn)
//          int index - chỉ số của phần tử hiện tại đang xét
int recursiveSum(const std::vector<int>& vec, int index) {
    // 1. Điều kiện dừng (Base Case)
    // Nếu chỉ số index đã vượt quá kích thước của vector, nghĩa là không còn phần tử nào để cộng.
    if (index >= vec.size()) {
        return 0; // Tổng của phần vector rỗng (từ index trở đi) là 0.
    }

    // 2. Trường hợp đệ quy (Recursive Case)
    // Cộng phần tử hiện tại (vec[index]) với tổng của phần còn lại của vector
    // (từ index + 1 đến hết). Lời gọi recursiveSum(vec, index + 1) là lời gọi đệ quy.
    else {
        return vec[index] + recursiveSum(vec, index + 1);
    }
}

int main() {
    std::vector<int> myVector = {1, 2, 3, 4, 5};
    std::vector<int> emptyVector;
    std::vector<int> singleElementVector = {10};

    // Bắt đầu tính tổng từ chỉ số 0
    std::cout << "Tong cac phan tu trong myVector: " << recursiveSum(myVector, 0) << std::endl; // Output: 15
    std::cout << "Tong cac phan tu trong emptyVector: " << recursiveSum(emptyVector, 0) << std::endl; // Output: 0
    std::cout << "Tong cac phan tu trong singleElementVector: " << recursiveSum(singleElementVector, 0) << std::endl; // Output: 10

    // Để so sánh với cách thông thường (không đệ quy)
    // int sum_iterative = 0;
    // for (int x : myVector) {
    //     sum_iterative += x;
    // }
    // std::cout << "Tong (khong de quy): " << sum_iterative << std::endl; // Output: 15

    // Hoặc dùng hàm có sẵn trong thư viện numeric
    // int sum_std = std::accumulate(myVector.begin(), myVector.end(), 0);
    // std::cout << "Tong (std::accumulate): " << sum_std << std::endl; // Output: 15


    return 0;
}

Giải thích Code:

• Hàm recursiveSum nhận vector và chỉ số index hiện tại. Chúng ta gọi ban đầu với index = 0.
• Điều kiện dừng: if (index >= vec.size()). Khi index bằng hoặc lớn hơn kích thước vector, nghĩa là chúng ta đã duyệt qua tất cả các phần tử hợp lệ và đã đến "phần rỗng" ở cuối vector. Hàm trả về 0.
• Trường hợp đệ quy: return vec[index] + recursiveSum(vec, index + 1);. Hàm lấy giá trị của phần tử tại index hiện tại (vec[index]) và cộng với kết quả của lời gọi đệ quy tới recursiveSum với chỉ số index + 1. Điều này hiệu quả là tính tổng của phần còn lại của vector.
• Mỗi lời gọi đệ quy tiến index lên 1, đảm bảo rằng chúng ta đang tiến dần về điều kiện dừng (index >= vec.size()).

Ví dụ 4: Tìm kiếm nhị phân (Binary Search) bằng Đệ quy

Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm kiếm một phần tử trong một mảng/vector đã được sắp xếp. Ý tưởng là liên tục chia đôi phạm vi tìm kiếm.

• Kiểm tra phần tử ở giữa phạm vi hiện tại.
• Nếu đó là phần tử cần tìm, trả về vị trí của nó (điều kiện dừng).
• Nếu phần tử cần tìm nhỏ hơn phần tử giữa, tìm kiếm tiếp tục ở nửa bên trái (trường hợp đệ quy).
• Nếu phần tử cần tìm lớn hơn phần tử giữa, tìm kiếm tiếp tục ở nửa bên phải (trường hợp đệ quy).

• Nếu phạm vi tìm kiếm trở nên rỗng (không còn phần tử nào để xét), phần tử không có trong mảng (điều kiện dừng).

• Trường hợp đệ quy: Tìm kiếm ở nửa trái hoặc nửa phải của phạm vi hiện tại. Phạm vi mới nhỏ hơn phạm vi ban đầu.

• Điều kiện dừng: Phần tử được tìm thấy HOẶC phạm vi tìm kiếm rỗng.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::sort nếu vector chưa sắp xếp

// Hàm tìm kiếm nhị phân sử dụng đệ quy
// Tham số: const std::vector<int>& arr - vector đã sắp xếp
//          int target - giá trị cần tìm
//          int low - chỉ số bắt đầu của phạm vi tìm kiếm hiện tại
//          int high - chỉ số kết thúc của phạm vi tìm kiếm hiện tại
int recursiveBinarySearch(const std::vector<int>& arr, int target, int low, int high) {
    // 1. Điều kiện dừng (Base Case 1): Phạm vi tìm kiếm rỗng
    // Nếu low > high, nghĩa là phạm vi tìm kiếm không hợp lệ (bắt đầu > kết thúc).
    // Điều này xảy ra khi phần tử không có trong vector.
    if (low > high) {
        return -1; // Trả về -1 để chỉ rằng không tìm thấy
    }

    // Tính chỉ số phần tử ở giữa
    // Sử dụng low + (high - low) / 2 để tránh tràn số với low và high lớn
    int mid = low + (high - low) / 2;

    // 2. Điều kiện dừng (Base Case 2): Phần tử được tìm thấy
    // Nếu phần tử ở giữa là phần tử cần tìm.
    if (arr[mid] == target) {
        return mid; // Trả về chỉ số của phần tử
    }

    // 3. Trường hợp đệ quy (Recursive Cases): Tiếp tục tìm kiếm ở nửa còn lại
    // Nếu phần tử cần tìm nhỏ hơn phần tử ở giữa, tìm kiếm ở nửa bên trái.
    else if (arr[mid] > target) {
        return recursiveBinarySearch(arr, target, low, mid - 1); // Gọi đệ quy với phạm vi [low, mid-1]
    }
    // Nếu phần tử cần tìm lớn hơn phần tử ở giữa, tìm kiếm ở nửa bên phải.
    else { // arr[mid] < target
        return recursiveBinarySearch(arr, target, mid + 1, high); // Gọi đệ quy với phạm vi [mid+1, high]
    }
}

int main() {
    std::vector<int> sortedVector = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 23;
    int target2 = 100;
    std::vector<int> emptyVector;

    // Tìm target1 trong sortedVector
    int index1 = recursiveBinarySearch(sortedVector, target1, 0, sortedVector.size() - 1);
    if (index1 != -1) {
        std::cout << "Tim thay " << target1 << " tai chi muc: " << index1 << std::endl; // Output: Tim thay 23 tai chi muc: 5
    } else {
        std::cout << "Khong tim thay " << target1 << " trong vector." << std::endl;
    }

    // Tìm target2 trong sortedVector
    int index2 = recursiveBinarySearch(sortedVector, target2, 0, sortedVector.size() - 1);
    if (index2 != -1) {
        std::cout << "Tim thay " << target2 << " tai chi muc: " << index2 << std::endl;
    } else {
        std::cout << "Khong tim thay " << target2 << " trong vector." << std::endl; // Output: Khong tim thay 100 trong vector.
    }

    // Tìm kiếm trong vector rỗng
     int index3 = recursiveBinarySearch(emptyVector, target1, 0, emptyVector.size() - 1); // emptyVector.size() - 1 sẽ là -1
     if (index3 != -1) {
         std::cout << "Tim thay " << target1 << " tai chi muc: " << index3 << std::endl;
     } else {
         std::cout << "Khong tim thay " << target1 << " trong vector rong." << std::endl; // Output: Khong tim thay 23 trong vector rong.
     }


    return 0;
}

Giải thích Code:

• Hàm recursiveBinarySearch nhận vector (arr), giá trị cần tìm (target), và phạm vi tìm kiếm hiện tại được xác định bởi low (chỉ số bắt đầu) và high (chỉ số kết thúc).
• Điều kiện dừng 1: if (low > high). Nếu low lớn hơn high, điều này có nghĩa là phạm vi tìm kiếm đã thu hẹp lại và không còn chứa phần tử nào nữa. Phần tử target không tồn tại trong vector, nên hàm trả về -1.
• Điều kiện dừng 2: if (arr[mid] == target). Nếu phần tử ở giữa (arr[mid]) bằng với target, chúng ta đã tìm thấy phần tử và trả về chỉ số mid.
• Trường hợp đệ quy:
  • Nếu arr[mid] > target, phần tử cần tìm (nếu có) phải nằm ở nửa bên trái của mid. Hàm gọi đệ quy tới recursiveBinarySearch với phạm vi mới là [low, mid - 1].
  • Nếu arr[mid] < target, phần tử cần tìm (nếu có) phải nằm ở nửa bên phải của mid. Hàm gọi đệ quy tới recursiveBinarySearch với phạm vi mới là [mid + 1, high].
• Mỗi lời gọi đệ quy thu hẹp phạm vi tìm kiếm (low và high tiến lại gần nhau), đảm bảo rằng chúng ta cuối cùng sẽ đạt đến một trong hai điều kiện dừng.

Những nguyên lý cần khắc cốt ghi tâm

Qua các ví dụ trên, bạn có thể thấy rõ hai nguyên lý không thể thiếu khi làm việc với đệ quy:

1. Phải có Điều kiện dừng (Base Case): Luôn xác định trường hợp đơn giản nhất của bài toán và đảm bảo hàm của bạn xử lý trường hợp đó trực tiếp mà không gọi đệ quy. Đây là lớp bảo vệ chống lại đệ quy vô hạn.
2. Phải tiến về Điều kiện dừng: Mỗi lần gọi đệ quy, bài toán con được giải quyết phải là một phiên bản nhỏ hơn hoặc đơn giản hơn của bài toán ban đầu, sao cho cuối cùng nó sẽ đạt đến điều kiện dừng. Ví dụ, giảm n xuống n-1, thu hẹp phạm vi tìm kiếm từ [low, high] xuống [low, mid-1] hoặc [mid+1, high].

Bài tập ví dụ:

Chuỗi GCD

Trong một nhiệm vụ mới, các anh hùng của FullHouse Dev đang phải đối mặt với một thử thách về xử lý chuỗi nhị phân. Họ cần phải tìm hiểu về mối quan hệ giữa các chuỗi GCD để giải mã một thông điệp bí ẩn. Với tinh thần không lùi bước, FullHouse Dev bắt đầu nghiên cứu vấn đề này.

Bài toán

Cho một chuỗi nhị phân \(P\) có độ dài \(N\). Ta định nghĩa \(P^\infty\) là một chuỗi vô hạn với \(P^\infty[i] = P[i \bmod N]\) (hiểu đơn giản là \(P^\infty\) là sự nối tiếp của \(P\) với chính nó vô số lần).

Định nghĩa chuỗi GCD của hai số nguyên \(a, b\) với \(a \geq b\) là một chuỗi nhị phân có độ dài \(a\) thỏa mãn:

• \(GCD(a,b) = 10^{b-1}\) (1 theo sau bởi \(b-1\) số 0) nếu \(a\) chia hết cho \(b\)
• \(GCD(a,b) = \) \(b\) ký tự đầu tiên của \(P^\infty\) trong trường hợp còn lại

Gọi \(val(s)\) là giá trị của số nguyên được biểu diễn bởi chuỗi nhị phân \(s\) trong hệ cơ số 2. Cho \(T\) cặp số nguyên \(a, b\), tính \(val(GCD(a,b))\) cho mỗi cặp.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Mỗi test case gồm một dòng chứa hai số nguyên \(a, b\)

OUTPUT FORMAT:

• In ra \(T\) dòng, mỗi dòng là kết quả \(val(GCD(a,b))\) tương ứng với mỗi test case

Ràng buộc:

Với tất cả các test:

• \(1 \leq T \leq 10^5\)
• \(1 \leq b \leq a \leq 10^9\)

File 1 (70 điểm):

• \(a \leq 10^3\)

File 2 (30 điểm):

• Không có ràng buộc thêm

Ví dụ

INPUT

5
3 1
3 2
5 2
10 4
100 3

OUTPUT

4
5
21
546
986497880

Giải thích

Kết quả trong hệ nhị phân cho bốn test case đầu tiên như sau:

• Test case 1: 100 (cơ số 2) = 4 (cơ số 10)
• Test case 2: 101 (cơ số 2) = 5 (cơ số 10)
• Test case 3: 10101 (cơ số 2) = 21 (cơ số 10)
• Test case 4: 1000100010 (cơ số 2) = 546 (cơ số 10) Dưới đây là hướng dẫn giải bài toán "Chuỗi GCD" một cách ngắn gọn, tập trung vào ý tưởng chính và cấu trúc giải thuật, không cung cấp code hoàn chỉnh.

Phân tích bài toán và các trường hợp:

1. Hiểu định nghĩa chuỗi GCD(a,b): Bài toán định nghĩa chuỗi GCD(a,b) có độ dài a. Có hai trường hợp:

   • Nếu a chia hết cho b (a % b == 0): Chuỗi là '1' theo sau bởi b-1 số '0'. Tuy nhiên, ví dụ (3,1) với a=3, b=1 (a%b==0) cho ra giá trị 4, tương ứng với chuỗi nhị phân 100 (độ dài 3 = a). Định nghĩa "10^{b-1}" (1 theo sau b-1 số 0) có vẻ chỉ mô tả phần đầu hoặc tính chất. Dựa vào ví dụ (3,1), ta suy luận rằng trong trường hợp a % b == 0, chuỗi có độ dài a và chỉ có bit đầu tiên (vị trí 0) là '1', các bit còn lại là '0'. Giá trị của chuỗi này là $2^{a-1}$.
   • Nếu a không chia hết cho b (a % b != 0): Định nghĩa nói là "b ký tự đầu tiên của $P^\infty$". Nhưng độ dài chuỗi kết quả phải là a. Các ví dụ (3,2), (5,2), (10,4) cho thấy chuỗi kết quả có độ dài a. Phân tích các chuỗi nhị phân trong ví dụ (101, 10101, 1000100010), ta thấy bit thứ i (0-indexed từ trái) là '1' nếu i chia hết cho b, và '0' nếu i không chia hết cho b. Chuỗi này có độ dài a.

2. Xác định quy tắc tạo chuỗi (Dựa trên suy luận từ ví dụ và độ dài a):

   • Trường hợp 1: a % b == 0 Chuỗi nhị phân có độ dài a. Bit tại vị trí 0 là '1', các bit còn lại (từ 1 đến a-1) là '0'. Giá trị của chuỗi: $2^{a-1}$.
   • Trường hợp 2: a % b != 0 Chuỗi nhị phân có độ dài a. Bit tại vị trí i (0-indexed từ trái, 0 \leq i < a) là '1' nếu i % b == 0, và '0' nếu i % b != 0$. Các vị trí có bit '1' là: $0, b, 2b, 3b, \dots, kb$ với $kb < a$. Vị trí lớn nhất là $b \cdot \lfloor (a-1)/b \rfloor$. Giá trị của chuỗi: Tổng của $2^{a-1-i}$ cho tất cả các vị tríi` mà bit tại đó là '1'. Giá trị = $\sum_{k=0}^{\lfloor (a-1)/b \rfloor} 2^{a-1-kb}$.

Chiến lược giải:

1. Xử lý trường hợp a % b == 0:

   • Kết quả là $2^{a-1}$.
   • Vì a có thể rất lớn ($10^9$), $2^{a-1}$ cũng rất lớn. Cần sử dụng kiểu dữ liệu số nguyên lớn (BigInt).
   • Tính $2^{a-1}$ sử dụng thuật toán bình phương và nhân (binary exponentiation) với BigInt.

2. Xử lý trường hợp a % b != 0:

   • Cần tính tổng $\sum_{k=0}^{\lfloor (a-1)/b \rfloor} 2^{a-1-kb}$.
   • Đặt $q = \lfloor (a-1)/b \rfloor$ và $r = (a-1) \% b$.
   • Tổng trở thành $\sum_{k=0}^{q} 2^{qb+r-kb} = 2^r \sum_{k=0}^{q} 2^{b(q-k)}$.
   • Đổi biến $j = q-k$. Khi $k=0, j=q$. Khi $k=q, j=0$.
   • Tổng trở thành $2^r \sum_{j=0}^{q} 2^{bj} = 2^r (2^{0} + 2^{b} + (2^{b})^2 + \dots + (2^{b})^q)$.
   • Đây là một tổng hình học với số hạng đầu $1$, công bội $X = 2^b$, và số lượng số hạng là $q+1$.
   • Giá trị cần tính là $2^r \cdot (1 + X + X^2 + \dots + X^q)$.
   • Vì a và b có thể lớn, X = 2^b và các lũy thừa của X cũng rất lớn. Cần sử dụng BigInt.
   • Số lượng số hạng trong tổng ($q+1$) có thể lên tới xấp xỉ $a/b$. Nếu $b=1$, $q \approx a$. Vòng lặp tính tổng trực tiếp sẽ quá chậm nếu a lớn ($10^9$).
   • Tổng hình học $1 + X + \dots + X^q$ có thể tính nhanh bằng thuật toán bình phương và nhân cho tổng (tương tự như tính lũy thừa, nhưng áp dụng cho tổng).
     • Đặt $S(q) = 1 + X + \dots + X^q$.
     • Nếu $q < 0$, $S(q) = 0$.
     • Nếu $q = 0$, $S(q) = 1$.
     • Nếu $q$ lẻ ($q=2m+1$): $S(q) = (1 + X + \dots + X^m) + X^{m+1}(1 + \dots + X^m) = S(m) + X^{m+1} S(m) = S(m)(1 + X^{m+1})$, với $m = q/2$.
     • Nếu $q$ chẵn ($q=2m$): $S(q) = (1 + \dots + X^{m-1}) + X^m(1 + \dots + X^m) = S(m-1) + X^m S(m)$, với $m=q/2$.
   • Sử dụng đệ quy hoặc lặp với BigInt để tính $S(q) = \text{FastSum}(X, q)$ trong $O(\log q)$ phép toán BigInt.
     • Hàm FastSum(X, q):
       • Nếu q < 0, trả về BigInt(0).
       • Nếu q == 0, trả về BigInt(1).
       • m = q / 2.
       • Sum_m = FastSum(X, m).
       • X_m = X.pow(m).
       • Nếu q % 2 == 1: Trả về Sum_m * (BigInt(1) + X_m * X).
       • Nếu q % 2 == 0: Trả về FastSum(X, m-1) * (BigInt(1) + X_m) + X_m.

3. Triển khai BigInt: Cần cài đặt các phép toán cơ bản cho số nguyên lớn: cộng, nhân, và lũy thừa (pow). Cần chú ý đến việc lưu trữ số lớn (ví dụ: dùng std::vector<int> lưu các chữ số trong hệ cơ số 10^9 hoặc 10^18).

Tóm tắt các bước giải:

1. Đọc số lượng test case T.
2. Với mỗi test case đọc a, b.
3. Nếu a % b == 0:
   • Tính BigInt result = BigInt(2).pow(a - 1).
4. Nếu a % b != 0:
   • Tính long long q = (a - 1) / b.
   • Tính long long r = (a - 1) % b.
   • Tính BigInt X = BigInt(2).pow(b).
   • Tính BigInt G = FastSum(X, q).
   • Tính BigInt pow2_r = BigInt(2).pow(r).
   • Tính BigInt result = pow2_r * G.
5. In ra result.

Làm thêm nhiều bài tập miễn phí tại đây