\(\color{red}{\text{Spoiler Alert - Số huyền bí MYSTERY}}\)

\(\color{Blue}{\text{Hướng dẫn}}\)

\(\color{Orange}{\text{Phương pháp 1: Cày trâu (Chạy đến N)}}\)

• Chạy \(d\) từ \(1\) đến \(N\), nếu \(d\) là ước của \(N\) thì \(res = res * (3^d - 1)\) \(mod\) \(20122007\).
• Độ phức tạp: \(O(N)\).
• Vậy với cách cày trâu này bạn không thể \(AC\) bài tập do giới hạn số quá lớn \((10^9)\), đã thế còn tính lũy thừa nữa, chắc chắn không thể \(AC\). Vậy ta sử dụng phương pháp \(2\).

\(\color{Orange}{\text{Phương pháp 2}}\)

• Với phương pháp \(2\), ta chỉ chạy đến \(sqrt(N)\), nếu \(d\) là ước của \(N\) thì gán res theo công thức \(3^d - 1\) \(mod\) \(20122007\) (nhớ phải \(mod\) vào nếu không sẽ bị \(WA\) đấy). Dĩ nhiên bạn cũng phải lấy giá trị của \(j = \frac{N}{d}\) nếu \(j > d\).
• Độ phức tạp \(O(sqrt(N))\).
• Tuy nhiên, nếu bạn vẫn không \(AC\) thì hãy xem tiếp để hiểu lí do nhé.

• Bạn không \(AC\) có thể chương trình của bạn gặp vấn đề với hàm số mũ của bạn. Có thể một số bạn sẽ viết hàm như thế này:

long long power(long long a, long long b) {
    long long result = 1;
    for(int i = 1; i <= b; i++) {
        result *= a;
    }
    return result % 20122007;
 }

Tuy nhiên bạn có thể bị \(TLE\) vì thời gian chạy khá lâu. Vì vậy bạn sẽ "rút gọn" lại hàm số mũ bằng nhận xét sau:

\(x^N=(x^\frac{N}{2})^2\) nếu \(N\) chẵn

\(x^N=x(x^\frac{N-1}{2})^2\) nếu \(N\) lẻ

Vậy ta biết được rồi thì việc code chúng ra là việc quá đơn giản:

int sqr(int x) {
    return x*x;
}

int mu(int a, int b) {
    if (b == 0) return 1;
    else
        if (b % 2 == 0)
            return sqr(mu(a, b/2)) % MOD;
        else
            return a * (sqr(mu(a, (b-1)/2))) % MOD;
}

• Tuy nhiên bạn cũng phải chú ý rằng mọi hành động trong hàm cũng như trong chương trình chính đều phải \(mod\) cho \(20122007\), chỉ cần thiếu \(1\) lần \(mod\) bạn sẽ sai nguyên bài.

• Phần code chính bạn sẽ tự làm.

Cảm ơn các bạn đã theo dõi phần \(Editorial\) của mình. Có gì sai sót hoặc không hiểu, các bạn cứ comment nhé, mình sẽ chỉnh sửa và giải thích cho các bạn!