Số huyền bí

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
corona
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ \(17\) cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn đường vào kho tàng của đất nước. Theo các chứng tích khảo cổ, các nhà khoa học kết luận rằng số huyền bí cơ sở \(a\) bằng tích của (\(3^{d}−1\)) với mọi ước số \(d>0\) của \(a\).

Bờm thích số học đồng thời cũng rất thích tìm hiểu lịch sử đất nước. Bạn hãy giúp Bờm tính số huyền bí cơ sở \(a\) (\(1 \leq a \leq 10^{9}\)). Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số huyền bí cơ sở a khi chia cho \(20122007\).

Input

  • Gồm một số nguyên \(a\) duy nhất.

Output

  • In ra số nguyên duy nhất là phần dư của số huyền bí cơ sở \(a\) khi chia cho \(20122007\).

Constraints

  • \(1 \leq a \leq 10^{9}\)

Example

Test 1

Input 
10
Output 
7291779

Bình luận


  • 1
    dang7rickroll    3:42 p.m. 14 Tháng 9, 2021

    \(\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:

    C++
    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!

    • 2 bình luận nữa