Iterated Linear Function

发表于 分类于 ，

    $f(x) = Ax+B$

    $g^{(0)}(x) = x, g^{(n)}(x) = f(g^{(n-1)}(x))$

    给出$A,B,n,x$求$g^{(n)}(x)\pmod {10^9+7}$

Iterated Linear Function

Created by LXC on Fri Jul 7 08:55:46 2023

https://codeforces.com/problemset/problem/678/D

ranting: 1700

tag: math, number theory

problem

$f(x) = Ax+B$

$g^{(0)}(x) = x, g^{(n)}(x) = f(g^{(n-1)}(x))$

给出$A,B,n,x$求$g^{(n)}(x)\pmod {10^9+7}$

solution

$g^{(0)}(x) = x$

$g^{(1)}(x) = Ax+B$

$g^{(2)}(x) = A(Ax+B)+B = A^2x+AB+B$

$g^{(3)}(x) = A(A(Ax+B)+B)+B = A^3x+A^2B+AB+B$

$\cdots$

$g^{(n)}(x) = A^nx+(A^{n-1}+A^{n-2}+\cdots+A^0)B=A^nx+\frac{A^n-1}{A-1}B$

需要用到快速幂，以及乘法逆元。乘法逆元可以基于费马小定理用快速幂求出。

当A-1为0是特殊判断，否则求A-1在模1e9+7下的逆元。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 1000000007
using namespace std;

ll fpow(ll a, ll p) {
    ll rt = 1;
    while (p) {
        if (p & 1)
            rt *= a, rt %= MOD;
        a *= a;
        a %= MOD;
        p >>= 1;
    }
    return rt;
}

void sol() {
    ll a, b, n, x;
    cin >> a >> b >> n >> x;
    ll p1 = fpow(a, n % (MOD - 1)) * x % MOD;
    ll p2 = b;
    if (a == 1)
        p2 = n % MOD * p2 % MOD;
    else
        p2 = p2 * (fpow(a, n % (MOD - 1)) - 1) % MOD * fpow(a - 1, MOD - 2) %
             MOD;
    cout << (p1 + p2) % MOD << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}