Wiki › Thuật toán › Toán học › Nội suy Lagrange

Nội suy Lagrange

huunguyen Updated Tháng sáu 1, 2026

Nội suy Lagrange (Lagrange interpolation) là kỹ thuật tìm đa thức $P (x)$ bậc $\leq N - 1$ duy nhất đi qua $N$ điểm $(x_{0}, y_{0}), \dots, (x_{N - 1}, y_{N - 1})$ , rồi tính giá trị của nó tại một điểm $x$ bất kỳ. Nó cho phép tính $P (x)$ trong $O (N^{2})$ ở trường hợp tổng quát, hoặc chỉ $O (N)$ khi các mốc $x_{i}$ là dãy số nguyên liên tiếp — thay vì phải khôi phục toàn bộ hệ số đa thức tốn $O (N^{2})$ rồi mới thay số.

Ứng dụng kinh điển nhất trong competitive programming: tính tổng $\sum_{i = 1}^{n} i^{k}$ hoặc $\sum_{i = 1}^{n} f (i)$ với $f$ là đa thức, khi $n$ lên tới $10^{18}$ — những bài mà vòng lặp trực tiếp $O (n)$ là bất khả thi.

Ý tưởng / Trực giác

Vì sao chỉ cần $N$ điểm là đủ? Một đa thức bậc $\leq N - 1$ có đúng $N$ hệ số $a_{0}, a_{1}, \dots, a_{N - 1}$ . Mỗi điểm $(x_{i}, y_{i})$ cho ta một phương trình tuyến tính theo các hệ số đó. $N$ điểm với các $x_{i}$ đôi một khác nhau cho $N$ phương trình độc lập, nên đa thức được xác định duy nhất. Đây là lý do "biết $N$ giá trị thì suy ra mọi giá trị khác".

Vì sao công thức Lagrange đúng? Thay vì giải hệ phương trình, Lagrange xây trực tiếp đa thức bằng cách ghép $N$ "viên gạch" $ℓ_{i} (x)$ , mỗi viên ứng với một điểm:

$ℓ_{i} (x) = \prod_{j \neq i} \frac{x - x_{j}}{x_{i} - x_{j}}$

Viên gạch $ℓ_{i}$ được thiết kế để có tính chất bộ lọc:

Tại $x = x_{i}$ : tử và mẫu giống hệt nhau nên $ℓ_{i} (x_{i}) = 1$ .
Tại $x = x_{m}$ với $m \neq i$ : trong tích có thừa số $(x_{m} - x_{m}) = 0$ nên $ℓ_{i} (x_{m}) = 0$ .

Nói cách khác $ℓ_{i} (x_{m}) = [i = m]$ . Vì vậy

$P (x) = \sum_{i = 0}^{N - 1} y_{i} \cdot ℓ_{i} (x)$

thỏa $P (x_{m}) = \sum_{i} y_{i} \cdot [i = m] = y_{m}$ tại mọi mốc. Mỗi $ℓ_{i}$ là đa thức bậc $N - 1$ , nên $P$ cũng bậc $\leq N - 1$ — đúng đa thức ta cần. Trực giác: $y_{i}$ chỉ được "kích hoạt" tại đúng điểm $x_{i}$ của nó, các điểm khác bị triệt tiêu về 0.

Vì sao tổng lũy thừa lại là đa thức? $S (n) = \sum_{i = 1}^{n} i^{k}$ là đa thức bậc $k + 1$ theo $n$ (định lý Faulhaber). Do đó chỉ cần tính $k + 2$ giá trị đầu tiên $S (1), S (2), \dots, S (k + 2)$ bằng cộng dồn, rồi nội suy tại $n$ khổng lồ. Ta không cần biết công thức đóng — chỉ cần "đủ điểm".

Ví dụ chạy tay

Cho 3 điểm $(1, 1), (2, 8), (3, 27)$ (chính là $y = x^{3}$ tại $x = 1, 2, 3$ ). Đa thức bậc $\leq 2$ qua 3 điểm này thực ra là $x^{3}$ thu hẹp — ta nội suy giá trị tại $x = 4$ (kết quả đúng phải là... lưu ý $x^{3}$ bậc 3 nên qua 3 điểm KHÔNG khôi phục được $x^{3}$ ; đa thức bậc 2 qua 3 điểm này sẽ cho giá trị khác $64$ tại $x = 4$ — chính minh hoạ rằng số điểm phải $\geq$ bậc+1).

Bố trí các mốc và việc tính từng viên gạch $ℓ_{i} (4)$ :

  i:        0        1        2
 x_i:       1        2        3
 y_i:       1        8       27
            |        |        |
   x = 4 ---+--------+--------+----> tính P(4)

Tính $ℓ_{0} (4) = \frac{(4 - 2) (4 - 3)}{(1 - 2) (1 - 3)} = \frac{2 \cdot 1}{(- 1) (- 2)} = \frac{2}{2} = 1$

Tính $ℓ_{1} (4) = \frac{(4 - 1) (4 - 3)}{(2 - 1) (2 - 3)} = \frac{3 \cdot 1}{(1) (- 1)} = \frac{3}{- 1} = - 3$

Tính $ℓ_{2} (4) = \frac{(4 - 1) (4 - 2)}{(3 - 1) (3 - 2)} = \frac{3 \cdot 2}{(2) (1)} = \frac{6}{2} = 3$

Ghép lại:

$P (4) = 1 \cdot 1 + 8 \cdot (- 3) + 27 \cdot 3 = 1 - 24 + 81 = 58$

Bảng tổng hợp từng bước (ô đang xét là cột $ℓ_{i} (4)$ ):

$i$	$x_{i}$	$y_{i}$	$ℓ_{i} (4)$	đóng góp $y_{i} \cdot ℓ_{i} (4)$
0	1	1	$1$	$1$
1	2	8	$- 3$	$- 24$
2	3	27	$3$	$81$
Σ				58

Kiểm chứng: đa thức bậc 2 qua 3 điểm trên là $P (x) = 6 x^{2} - 11 x + 6$ ; thật vậy $P (1) = 1, P (2) = 8, P (3) = 21$ ... khoan, $P (3) = 6 \cdot 9 - 33 + 6 = 27$ ✓. Và $P (4) = 96 - 44 + 6 = 58$ ✓. Khớp với nội suy.

Cài đặt

Tổng quát — $O (N^{2})$ với $N$ điểm bất kỳ

const long long MOD = 1e9 + 7;

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    if (a < 0) a += mod;                 // phòng a âm
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
// Nghịch đảo modulo: chỉ đúng khi MOD là số nguyên tố (Fermat nhỏ)
long long inv(long long a) { return power(a, MOD - 2, MOD); }

// Nội suy giá trị P(x) từ N điểm (xi[i], yi[i])
long long lagrange(vector<long long>& xi, vector<long long>& yi, long long x) {
    int n = xi.size();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long num = yi[i] % MOD, den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            // tử nhân (x - x_j), giữ trong [0, MOD)
            num = num * (((x - xi[j]) % MOD + MOD) % MOD) % MOD;
            // mẫu nhân (x_i - x_j)
            den = den * (((xi[i] - xi[j]) % MOD + MOD) % MOD) % MOD;
        }
        ans = (ans + num % MOD * inv(den)) % MOD; // chia = nhân nghịch đảo
    }
    return ans;
}

Nhanh — $O (N)$ khi $x_{i} = 0, 1, 2, \dots, N - 1$

Khi mốc liên tiếp, tích $\prod_{j \neq i} (x - j)$ được tách thành prefix $\prod_{j < i} (x - j)$ và suffix $\prod_{j > i} (x - j)$ tính một lần; còn mẫu $\prod_{j \neq i} (i - j) = (- 1)^{N - 1 - i} i! (N - 1 - i)!$ dùng giai thừa.

// Nội suy tại x từ N điểm (0, y[0]), (1, y[1]), ..., (N-1, y[N-1])
long long lagrange_consec(vector<long long>& y, long long x) {
    int n = y.size();
    x = ((x % MOD) + MOD) % MOD;

    // pre[i] = tích (x-0)(x-1)...(x-(i-1)) ; suf[i] = (x-i)...(x-(n-1))
    vector<long long> pre(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++)
        pre[i + 1] = pre[i] * ((x - i + MOD) % MOD) % MOD;
    for (int i = n - 1; i >= 0; i--)
        suf[i] = suf[i + 1] * ((x - i + MOD) % MOD) % MOD;

    // tiền xử lý giai thừa và nghịch đảo giai thừa
    vector<long long> fact(n, 1), inv_fact(n, 1);
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % MOD;
    inv_fact[n - 1] = power(fact[n - 1], MOD - 2, MOD);
    for (int i = n - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long num = pre[i] * suf[i + 1] % MOD;       // bỏ qua thừa số (x-i)
        long long den = inv_fact[i] * inv_fact[n - 1 - i] % MOD;
        if ((n - 1 - i) & 1) den = MOD - den;            // dấu (-1)^(n-1-i)
        ans = (ans + y[i] % MOD * num % MOD * den) % MOD;
    }
    return ans;
}

Ứng dụng: tổng lũy thừa $\sum_{i = 1}^{n} i^{k}$

$S (n)$ là đa thức bậc $k + 1$ nên cần $k + 2$ điểm:

long long sum_of_powers(long long n, int k) {
    int pts = k + 2;                 // số điểm = bậc + 1
    vector<long long> y(pts);
    long long cur = 0;
    for (int i = 1; i <= pts; i++) { // y[i-1] = S(i) = tổng dồn
        cur = (cur + power(i, k, MOD)) % MOD;
        y[i - 1] = cur;
    }
    // mốc của ta là x=1..pts; lagrange_consec dùng mốc 0..pts-1,
    // nên nội suy tại (n-1): điểm 0 ứng S(1), điểm pts-1 ứng S(pts)
    if (n <= pts) return y[n - 1];
    return lagrange_consec(y, (n - 1) % MOD);
}

Độ phức tạp

Phương pháp	Thời gian	Bộ nhớ
Tổng quát ( $N$ điểm bất kỳ)	$O (N^{2})$	$O (N)$
$x_{i}$ liên tiếp	$O (N)$	$O (N)$

Vì sao $O (N^{2})$ ở bản tổng quát? Với mỗi trong $N$ điểm, tích chạy qua $N - 1$ điểm còn lại → $N \cdot (N - 1)$ phép nhân. Nếu mỗi vòng lại gọi inv (lũy thừa nhanh $O (\log M O D)$ ) thì thành $O (N^{2} \log M O D)$ — vẫn coi là $O (N^{2})$ vì $\log M O D \approx 30$ là hằng số nhỏ, nhưng nên gộp nghịch đảo bằng tích tiền tố nếu muốn chặt chẽ.

Vì sao $O (N)$ ở bản liên tiếp? Prefix/suffix và giai thừa đều tính trong một lượt $O (N)$ ; nghịch đảo giai thừa chỉ tốn một lần lũy thừa nhanh $O (\log M O D)$ rồi truy hồi ngược $O (N)$ . Vòng tổng cuối là $O (N)$ . Bộ nhớ $O (N)$ cho các mảng pre, suf, fact, inv_fact.

⚠️ Lỗi thường gặp

Modulo âm khi tính $(x - x_{j})$ : $x - x_{j}$ có thể âm, a % MOD trong C++ trả số âm. Luôn dùng ((x - xj) % MOD + MOD) % MOD. Quên bước này → kết quả sai ngẫu nhiên, khó debug.
Nghịch đảo khi MOD không nguyên tố: inv(a) = power(a, MOD-2) (Fermat nhỏ) chỉ đúng khi MOD nguyên tố và $gcd (a, M O D) = 1$ . Nếu MOD hợp số (vd $2^{64}$ , hay modulo bài cho không nguyên tố) phải dùng nghịch đảo qua thuật toán Euclid mở rộng, hoặc đảm bảo phép chia là chia hết thật.
$x$ trùng một mốc $x_{i}$ : khi đó tồn tại thừa số $(x - x_{i}) = 0$ ở tử của các viên gạch khác và $ℓ_{i} (x) = 1$ ; công thức vẫn đúng nhưng nếu cài bản $O (N)$ mà không xử lý, mẫu có thể dính 0. An toàn nhất: nếu $x$ là số nguyên trong $[0, N - 1]$ thì trả thẳng $y [x]$ .
Lệch mốc (off-by-one) ở tổng lũy thừa: $S (i)$ ứng với $i = 1, 2, \dots$ nhưng lagrange_consec dùng mốc $0, 1, \dots$ . Phải nội suy tại $(n - 1)$ chứ không phải $n$ . Sai chỗ này cho kết quả lệch đúng một bậc, dễ qua test nhỏ nhưng sai test lớn.
Thiếu số điểm so với bậc: đa thức bậc $d$ cần $d + 1$ điểm. Tổng $\sum i^{k}$ là bậc $k + 1$ → cần $k + 2$ điểm; lấy thiếu (vd $k + 1$ ) sẽ nội suy nhầm sang đa thức bậc thấp hơn và sai. Khi không chắc bậc, lấy dư vài điểm cho an toàn.
Tràn số: mọi tích trung gian phải long long và % MOD ngay sau mỗi phép nhân; int * int với MOD $\approx 10^{9}$ tràn ngay. Đừng cộng dồn nhiều tích rồi mới lấy modulo một lần.

Biến thể / Mở rộng

Nội suy với mốc cách đều bước $h$ ( $x_{i} = x_{0} + i h$ ): tương tự bản liên tiếp, chỉ cần chia thêm lũy thừa của $h$ .
Lấy hệ số đa thức thay vì giá trị tại một điểm: cần khai triển tích $\prod (x - x_{j})$ — tốn $O (N^{2})$ và thường không cần trong CP.
Liên hệ: kỹ thuật này thường đi kèm tính nhanh giai thừa / nghịch đảo modulo và lũy thừa nhanh — xem Toán học để ôn lại số học modulo nền tảng.

Bài tập luyện

Lưu ý: pool CTOJ hiện chưa có bài chuyên về nội suy Lagrange. Dưới đây là các bài rèn bộ công cụ số học modulo (lũy thừa nhanh, nghịch đảo, đếm theo modulo số nguyên tố, công thức đóng tại $n$ lớn) — nền tảng bắt buộc trước khi áp dụng Lagrange.

Lũy thừa modulo (modexp) — (Amateur) Rèn hàm power(a, b, MOD) — chính là engine để tính nghịch đảo modulo dùng khắp nơi trong Lagrange.
Đếm lưới ô vuông (cntgrids) — (Advanced) Đếm theo công thức đóng modulo $10^{9} + 7$ với $n$ tới $10^{9}$ , luyện tư duy "tính đại lượng tại $n$ rất lớn" bằng lũy thừa modulo.
Số học mô-đun (modarith) — (Advanced) Đếm số hàm modulo một số nguyên tố lẻ; củng cố thao tác nghịch đảo và đếm dưới modulo nguyên tố — đúng bộ kỹ năng Lagrange yêu cầu.