Hướng dẫn AC bài XGCD

Persia 2024-05-07 13:29:50 2024-05-07 13:30:23

Sub1: Backtrack sinh tất cả các dãy. Độ phức tạp O(m^n)

Sub2: Quy hoạch động, gọi F(i) là số dãy độ dài i thõa mãn đến i, gọi cnt là số các số j sao cho gcd(j, b(i - 1)) = b(i), ta có F(i) = cnt * F(i - 1), tính cnt bằng 1 vòng for. Độ phức tạp O(N x m)

Sub3: Dùng bao hàm loại trừ để tính cnt. Độ phức tạp khoảng O(N * 256)