\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Approach List}}\)

• Gọi \(res\) là kết quả \((x \times ... \times x) \mod (10^9 + 7)\) (\(n\) lần)

Hoặc là rảnh thì làm bignum rồi chia lấy dư xuống

Hoặc là đơn giản vừa nhân vừa lấy modulo xuống theo tính chất modulo

Hoặc có thể nâng cấp kiểu dữ liệu: Ghép 2 phần \(high\) và \(low\) (nếu có gì mình link tới editorial khác sau)

\(\color{goldenrod}{\text{Approach <Divide and conquer>}}\)

• Công thức toán chính

Khi \(n = 0\) thì \(res = x ^ 0 = 1\)

Khi \(n\) chẵn thì \(x \times n = x ^ {\lfloor \frac{n}{2} \rfloor} + x ^ {\lfloor \frac{n}{2} \rfloor}\)

Khi \(n\) lẻ thì \(x \times n = x ^ {\lfloor \frac{n}{2} \rfloor} + x ^ {\lfloor \frac{n}{2} \rfloor} + x\)

• Công thức toán dưới modulo (để tránh thành số lớn)

Khi \(n = 0\) thì \(res = x ^ 0 \mod m = 1\)

Khi \(n\) chẵn hay \(n \equiv 0 \pmod 2\) thì \((x ^ n) \mod m = ((x ^ {\lfloor \frac{n}{2} \rfloor} \mod m) + (x ^ {\lfloor \frac{n}{2} \rfloor} \mod m)) \mod m\)

Khi \(n\) lẻ hay \(n \equiv 1 \pmod 2\) thì \((x ^ n) \mod m = ((x ^ {\lfloor \frac{n}{2} \rfloor} \mod m) + (x ^ {\lfloor \frac{n}{2} \rfloor} \mod m) + (x \mod m)) \mod m\)

\(\color{green}{\text{Preference AC Code }}\): Divide and conquer

\(^{^{\color{purple}{\text{Complexity : }} O(\log n)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int mulMOD(int a, int b, int m = MOD) { return (1LL * a * b) % m; }
int powMOD(int x, int n, int m = MOD)
{
    int res = 1;
    while (n > 0) {
        if (n % 2 == 1)
            res = mulMOD(res, x, m);

        x = mulMOD(x, x, m);
        n /= 2;
    }

    return res;
}

\(\color{green}{\text{Preference AC Code }}\): Bitwise, Divide and conquer

\(^{^{\color{purple}{\text{Complexity : }} O(\log n)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int mulMOD(int a, int b, int m = MOD) { return (1LL * a * b) % m; }
int powMOD(int x, int n, int m = MOD)
{
    int res = 1;
    while (n > 0) {
        if (n & 1)
            res = mulMOD(res, x, m);

        x = mulMOD(x, x, m);
        n >>= 1;
    }

    return res;
}

\(\color{green}{\text{Preference AC Code }}\): Bitwise, Divide and conquer

\(^{^{\color{purple}{\text{Complexity : }} O(\log n)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int mulMOD(int a, int b, int m = MOD) { return (1LL * a * b) % m; }
int powMOD(int x, int n, int m = MOD)
{
    int res = 1;
    for (x %= m; n > 0; x = mulMOD(x, x, m), n >>= 1)
        if (n & 1) res = mulMOD(res, x, m);

    return res;
}

\(\color{purple}{\text{Question}}\)

• Phía trên là cách để tính \(((x ^ n) \mod m)\) bằng khử đệ quy, liệu bạn có thể làm đệ quy chứ ?

\(\color{purple}{\text{Author Question}}\)

• Mình không rõ có cách nào để Deep-optimize (hạn chế modulo) như bài hướng dẫn này hay không