Subtask 1

Trâu, lưu ý modulo

Subtask 2

Theo đề bài: \(g_0(x)=x\) và \(g_n(x)=f\left(g_{n-1}(x)\right)\) với \(n \ge 1\),
\(\rightarrow g_1(x)=f(g_0(x))=f(x)=Ax+B\)
\(\rightarrow g_2(x)=f(g_1(x))=A(Ax+B)+B=A^2 x + AB + B\)
...
\(\begin{array}{l} {g_n}\left( x \right) = A\left( {A\left( {A\left( {...\left( {Ax + B} \right) + B} \right) + B} \right) + ...} \right) + B\\ = {A^n}x + {A^{n - 1}}B + {A^{n - 2}}B + ... + B\\ = {A^n}x + B\left( {{A^{n - 1}} + {A^{n - 2}} + ... + A + 1} \right)\\ = {A^n}x + \frac{{B\left( {{A^{n - 1}}} \right)}}{{A - 1}} \end{array}\)
(do \({A^n} - 1 = \left( {A - 1} \right) \times \left( {{A^{n - 1}} + {A^{n - 2}} + ... + A + 1} \right)\)).

Quay về với yêu cầu, đề yêu cầu tính \({g_n}\left( x \right){\rm{mod }}\left( {{{10}^9} + 7} \right)\):
\({g_n}\left( x \right)\% \bmod = \left( {{A^n}\% \bmod } \right) \times \left( {x\% \bmod } \right) + \left( {B\% \bmod } \right) \times \left( {\frac{{{A^n} - 1}}{{A - 1}}} \right)\% \bmod\).

• Tính \({a^n}\% \bmod\) sử dụng chia để trị;
• Tính \(\left( {\frac{{{A^{n - 1}}}}{{A - 1}}} \right)\% \bmod\): Ta có định lý Fermat nhỏ: Nếu \(p\) là số nguyên tố thì với số tự nhiên \(b\) ta có \(b^{n-1}\%p=0\).
• Áp dụng: với \(p\) là số nguyên tố ta có \(\left( {\frac{a}{b}} \right)\% p = \left( {\frac{{a \times {b^{p - 2}}}}{{{b^{p - 1}}}}} \right)\% p = \left( {a \times {b^{p - 2}}} \right)\% p\) (đồng dư)

\(\begin{array}{l} \to {g_n}\left( x \right)\% \left( {{{10}^9} + 7} \right) = \left( {{A^n}\% \bmod } \right) \times \left( {x\% \bmod } \right) + \left( {B\% \bmod } \right) \times \left( {\left( {\frac{{{A^n} - 1}}{{A - 1}}} \right)\% \bmod } \right)\\ = \left( {{A^n}\% \bmod } \right) \times \left( {x\% \bmod } \right) + \left( {B\% \bmod } \right) \times \left( {\left( {\left( {{A^n} - 1} \right) \times {{\left( {A - 1} \right)}^{\bmod - 2}}} \right)\% \bmod } \right) \end{array}\)

Tổng kết: Bài này chủ yếu nghiêng về toán và modulo, nên các bạn giỏi toán có thể dễ dàng tìm ra được công thức và cài đặt bằng thuật toán phù hợp.

Code tham khảo:

Solution

C++

int po (int k, int h)
{
    if (h == 0)
    {
        return 1;
    }
    else
    {
        int temp = po(k, h / 2) % MOD;
        if (h % 2 == 0)
        {
            return temp * temp % MOD % MOD;
        }
        else
        {
            return (temp * temp % MOD) * k % MOD;
        }
    }
}

main()
{
    if (/*điều kiện gì đó*/)
    {
        // làm gì đó
    }
    else
    {
        // làm gì đó
    }
}