+8

Công thức toán và tính chất số học - Những thứ kỳ lạ trong Tin học (Phần 1)

I. Lời mở đầu

Xét bài toán sau đây: Tính giá trị biểu thức:

S=12+22++N2,với 1N109S = 1^2 + 2^2 + \cdots + N^2, \text{với }1 \le N \le 10^9

Đối với những ai đã tiếp cận với ngôn ngữ lập trình, hẳn ban đầu sẽ thấy bài toán này rất đơn giản. Chỉ cần chạy một vòng lặp biến ii với ii từ 11 tới N,N, rồi gán S=S+(ii)S=S+(i * i) là xong! Nhưng sự thật có đơn giản như vậy? Ta để ý thấy giới hạn NN của bài toán lên đến 109,10^9, do đó nếu thực hiện vòng lặp từ 11 tới NN sẽ khiến cho thời gian thực thi chương trình không đảm bảo.

Vậy giải pháp là gì? Lúc này những bạn học sinh nào có nền tảng toán chắc chắn sẽ biết ngay công thức tổng quát của SSN(N+1)(2N+1)6,\frac{N(N+1)(2N+1)}{6}, từ đây có thể tính được SS chỉ trong một phép tính. Thậm chí nếu nâng cấp bài toán lên thành tìm số dư của SS sau khi chia cho một số nguyên tố nào đó, thì chúng ta vẫn giải quyết được rất nhanh nếu như đã nắm được kiến thức về Nghịch đảo modulo.

Như vậy, điểm mấu chốt của bài toán không nằm ở cách tính, mà nằm ở việc làm sao để tìm ra công thức tổng quát? Trong lập trình thi đấu có vô số những bài toán oái ăm kiểu như vậy, từ vấn đề dễ dàng nhất là tìm công thức tổng quát của các dãy số, cho đến những thứ "khó nhằn" như phải áp dụng các tính chất số học, các định lý, tiên đề, bổ đề,...kỳ lạ mà có tìm mỏi mắt cũng không thấy trong các cuốn sách Toán bậc Trung học. Và thực tế trong các kỳ thi đã cho thấy, khi gặp những bài toán kiểu này, số lượng các bạn học sinh chứng minh được hoàn thiện một công thức là rất ít. Chủ yếu các bạn sẽ làm dựa vào cảm quan (nhìn ra công thức rồi làm cầu may rằng nó đúng), hoặc nếu tình cờ đã biết công thức từ trước thì...lấy được điểm.

Từ kinh nghiệm của bản thân và đúc kết qua nhiều kỳ thi HSG Tin học, mình quyết định cho ra đời chuyên đề này nhằm hỗ trợ các bạn học sinh chuyên Tin trong quá trình giải những bài toán về công thức Toán hoặc tính chất số học, giúp các bạn biết được nhiều hơn về những lý thuyết số học có thể không bao giờ được học trong Toán nhưng lại xuất hiện thường xuyên trong Tin học. Hy vọng sẽ giúp các bạn tiếp cận các bài toán về số học tốt hơn.

Trước khi tiếp cận chuyên đề này, các bạn nên hiểu sơ lược về những kiến thức trong Toán học như Phương pháp chứng minh Quy nạp, Bất đẳng thức, Tiên đề, Định lý và Bổ đề. Và tất nhiên, cả toán tổ hợp cũng sẽ cần thiết cho việc chứng minh các công thức. Ok, giờ thì bắt đầu thôi!

II. Những kiến thức Toán cần nắm vững

Trước tiên, mình sẽ nhắc lại một vài khái niệm toán học quan trọng mà các bạn nên nắm vững để thuận tiện hơn trong quá trình nghiên cứu chuyên đề. Tất nhiên đây không phải một bài giảng về Toán học, do đó mình sẽ cố gắng nói ngắn gọn nhất có thể (và sẽ bỏ qua công đoạn chứng minh nếu không cần thiết).

1. Phương pháp Quy nạp toán học

Phương pháp chứng minh Quy nạp toán học là phương pháp để chứng minh một mệnh đề đúng với nN\forall n \in N^{*} thông qua 33 bước:

  • Bước 11: Kiểm tra mệnh đề đúng với n=1n=1.
  • Bước 22: Giả sử mệnh đề đúng với n=k1n=k \ge 1 (Gọi là giả thiết quy nạp).
  • Bước 33: Chứng minh mệnh đề đúng với n=k+1n=k+1.

Lưu ý, trong trường hợp cần chứng minh một mệnh đề đúng với mọi số tự nhiên npn \ge p (pp là số tự nhiên) thì thuật toán là:

  • Bước 11: Kiểm tra mệnh đề đúng với n=pn = p.
  • Bước 22: Giả sử mệnh đề đúng với n=k1n=k≥1 (giả thiết quy nạp)
  • Bước 33: Cần chứng minh mệnh đề đúng với n=k+1n=k+1.

Rất nhiều các dãy số có được công thức tổng quát là nhờ vào phương pháp Quy nạp toán học. Bạn đọc hết sức lưu ý phương pháp quan trọng này.

2. Tiên đề, định lý và bổ đề

Tiên đề (Định đề - Axioms): Là những phát biểu được coi là đúng, làm cơ sở cho các suy luận tiếp theo. Ví dụ như Hệ tiên đề Euclid hay Hệ tiên đề số học,...

Định lý (Theorems): Một định lý là một mệnh đề mà tính đúng đắn của nó có được thông qua việc chứng minh dựa trên các tiên đề và quy tắc suy luận. Ví dụ như Định lý Pythagoras hay Định lý Fermat. Chúng ta được phép sử dụng luôn các định lý mà không cần chứng minh lại.

Bổ đề (Lemmas): Có thể xem một bổ đề như một tiền định lý, nó là một giả thuyết đã được chứng minh hoặc chắc chắn sẽ được chứng minh, sử dụng để làm nền tảng cho các kết quả cao hơn. Giữa Bổ đề và Định lý không có sự phân biệt rõ ràng, nhưng thường thì các Bổ đề sẽ được dùng để chứng minh các Định lý. Một vài bổ đề nổi tiếng có thể kể đến là Bổ đề Harmonic, Bổ đề phép chia hay Bổ đề Burnside,...

Ngoài ra, còn những khái niệm khác như Giả thuyết (Phỏng đoán) hay Quy tắc,...nhưng đều rất đơn giản nên không cần đề cập tới.

III. Các công thức và hàm Toán học quan trọng trong Tin học

1. Phi hàm Euler

1.1. Định nghĩa

Phi hàm Euler của N,N, viết tắt là ϕ(N)\phi(N) - là số lượng các số nguyên dương không vượt quá NN và nguyên tố cùng nhau với NN. Công thức thường gặp của phi hàm Euler là:

ϕ(N)=N×pN(11p)\phi(N) = N\times\prod_{p|N}(1-\frac{1}{p})

với pp là các ước nguyên tố của NN.

Cài đặt: Dưới đây là chương trình tính phi hàm Euler với độ phức tạp O(N)O(\sqrt{N}). Bạn đọc hoàn toàn có thể cải tiến độ phức tạp thành O(log(N))O(\log(N)) bằng việc phân tích thừa số nguyên tố sử dụng sàng Eratosthenes trong những trường hợp cụ thể.

int phi_euler(int N)
{
    int res = N;
    for (int i = 2; i * i <= N; ++i)
        if (N % i == 0)
        {
            res -= res / i;

            while (N % i == 0)
                N /= i;
        }

    if (N > 1)
        res -= res / N;

    return res;
}

Trong một số trường hợp đặc biệt, ϕ(N)\phi(N) có thể tính nhanh như sau:

  • Nếu NN là một số nguyên tố: ϕ(N)=N1\phi(N) = N-1.
  • Nếu N=pkN=p^k với p là một số nguyên tố: ϕ(N)=pk1×(p1)\phi(N) = p^{k - 1}\times (p - 1).

1.2. Tính phi hàm Euler cho mọi số từ 11 tới NN

Như đã đề cập bên trên, công thức của phi hàm Euler là:

For performance reasons, math blocks are limited to 1000 characters. Try splitting up this block, or include an image instead.

với Npi\left \lfloor{\frac{N}{p^i}} \right \rfloor là giá trị phần nguyên của Npi\frac{N}{p^i} \cdot

Như vậy, Npi\left \lfloor{\frac{N}{p^i}} \right \rfloor sẽ bằng 00 với i:pi>N\forall i:p^i > N.

Chứng minh: Từ 11 tới N,N, cứ pp số liên tiếp chắc chắn sẽ có một số chia hết cho p,p, do đó số lượng số chia hết cho pp từ 11 tới NNNp\left \lfloor{\frac{N}{p}} \right \rfloor. Tương tự ta có số lượng số chia hết cho p2,p3,...p^2, p^3,... lần lượt là Np2,Np3,...\left \lfloor{\frac{N}{p^2}} \right \rfloor, \left \lfloor{\frac{N}{p^3}} \right \rfloor,... Vậy νp(N!)=Np+Np2+Np3+\nu_p(N!)=\left \lfloor{\frac{N}{p}} \right \rfloor + \left \lfloor{\frac{N}{p^2}} \right \rfloor + \left \lfloor{\frac{N}{p^3}} \right \rfloor+ \cdots

Cài đặt:

int legrende_formula(int N, int p)
{
    int res = 0;
    while (N > 0)
    {
        res += (N / p);
        N /= p; // Đếm số lượng số chia hết cho p, p^2, p^3,...
    }

    return res;
}

Giải thuật có độ phức tạp rơi vào khoảng O(logp(N))O(\log_p(N)).

2.2. Áp dụng với hợp số

Trong trường hợp bài toán thay đổi thành tìm kk lớn nhất sao cho N!N! chia hết cho MkM^k với MM là một hợp số, ta vẫn áp dụng được công thức Legendre để giải quyết bài toán. Giả sử MM phân tích ra thừa số nguyên tố có dạng:

M=p1r1×p2r2×pnrnM=p_1^{r_1} \times p_2^{r_2} \times \cdots p_n^{r_n}

thì kết quả bài toán sẽ là minνpi(N!)ri;i:1in\min \left \lfloor{\frac{\nu_{p_i}(N!)}{r_i}} \right \rfloor; \forall i: 1 \le i \le n.

Chứng minh: Giả sử N!N! phân tích ra thừa số nguyên tố có dạng:

N!=p1r1×p2r2×pnrnN!=p_1^{r'_1} \times p_2^{r'_2} \times \cdots p_n^{r'_n}

Để MkM^k là ước của N!N! thì:

k.r1r1;k.r2r2;...;k.rnrnk.r_1 \le r'_1; k.r_2 \le r'_2;...; k.r_n \le r'_n

Nói cách khác, νpi(N!)=riri\nu_{p_i}(N!)=\left \lfloor{\frac{r'_i}{r_i}} \right \rfloor. Từ đó suy ra kmax=minνpi(N!)ri;i:1ink_{max}=\min\left \lfloor{\frac{\nu_{p_i}(N!)}{r_i}} \right \rfloor; \forall i: 1 \le i \le n.

Cài đặt: Chương trình dưới đây sử dụng lại code tính công thức Legendre với số nguyên tố ở trên.

int legendre_for_composite(int N, int M)
{
    int res = 0;
    for (int i = 2; i * i <= M; ++i)
        if (M % i == 0)
        {
            int cnt_div = 0;
            while (M % i == 0)
            {
                ++cnt_div; 
                M /= i;
            }

            res = max(res, legrende_formula(N, i) / cnt_div);
        }

    return res;
}

2.3. Ứng dụng tìm số ước của N!N!

Một ứng dụng hay của công thức Legendre là tìm số ước của N!N!. Ta đã biết một số nguyên dương khi được phân tích dưới dạng p1r1×p2r2××pnrnp_1^{r_1} \times p_2^{r_2} \times \cdots \times p_n^{r_n} thì tổng số ước nguyên dương của nó sẽ là (r1+1).(r2+1)...(rn+1)(r_1 + 1).(r_2+1)...(r_n+1). Như vậy mục tiêu là tìm số mũ lớn nhất của các số nguyên tố pp trong N!N!, ta có thể áp dụng công thức Legendre như sau:

  • Bước 11: Sàng lọc số nguyên tố từ 11 tới N,N, lưu vào một mảng/vector.
  • Bước 22: Với mỗi số nguyên tố pp không vượt quá N,N, tìm νp(N!),\nu_p(N!), đó chính là số mũ của số nguyên tố pp trong phân tích của N!.N!. Kết quả cuối cùng sẽ là p(νp(N!)+1),\prod_{p}(\nu_p(N!) + 1), với pp là các số nguyên tố từ 11 tới NN.

Cài đặt: Giải thuật dưới đây có độ phức tạp tổng quát là O(N.log(N))O(N.\log(N)):

vector < int > eratosthenes_sieve(int limit) // Sàng lọc số nguyên tố.
{
    vector < bool > is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = true;

    for (int i = 2; i * i <= limit; ++i)
        if (is_prime[i])
            for (int j = i * i; j <= limit; j += i)
                is_prime[j] = false;

    vector < int > prime;
    for (int i = 2; i <= limit; ++i)
        if (is_prime[i])
            prime.push_back(i);

    return prime;
}

int factorial_cnt_divisors(int N) // Đếm số ước của N!
{
    vector < int > prime = eratosthenes_sieve(N);

    int div_cnt = 1;
    for (int p: prime)
        div_cnt *= (legendre_formula(N, p) + 1);

    return div_cnt;
}

3. Đếm số cặp nghiệm nguyên của phương trình 1x+1y=1N\frac{1}{x}+\frac{1}{y}=\frac{1}{N}

Bài toán đặt ra là với số nguyên dương NN cho trước, đếm số lượng cặp nghiệm nguyên dương (x,y)(x, y) thỏa mãn phương trình: 1x+1y=1N\frac{1}{x}+\frac{1}{y}=\frac{1}{N} \cdot Biến đổi phương trình như sau:

1x+1y=1N\frac{1}{x}+\frac{1}{y}=\frac{1}{N} x+yxy=1N\Leftrightarrow \frac{x+y}{xy}=\frac{1}{N} xyN.(x+y)=0\Leftrightarrow xy-N.(x+y)=0

Thêm N2N^2 vào cả hai vế, ta có:

xyN.(x+y)+N2=N2\Leftrightarrow xy-N.(x+y)+N^2=N^2 xyNxNy+N2=N2\Leftrightarrow xy-Nx-Ny+N^2=N^2 x.(yN)N.(yN)=N2\Leftrightarrow x.(y-N)-N.(y-N)=N^2 (yN).(xN)=N2\Leftrightarrow (y-N).(x-N)=N^2

Từ đây ta thấy số cặp nghiệm nguyên dương của phương trình chính là số ước nguyên dương của N2,N^2, vì ứng với một ước ii của N2N^2 thì sẽ có một ước nữa là Ni,\frac{N}{i}, khi đó (yN)=i(y-N)=i(xN)=Ni(x-N)=\frac{N}{i} \cdot

Cài đặt: Dưới đây là chương trình đếm số cặp nghiệm nguyên dương của phương trình bằng phương pháp phân tích thừa số nguyên tố:

int count_solutions(int N)
{
    // Tổng số cặp nghiệm của phương trình, cũng là số ước của N^2.
    int total_solutions = 1; 
    for (int i = 2; i * i <= N; ++i)
        if (N % i == 0)
        {
            int power = 0;
            while (N % i == 0)
            {
                ++power;
                N /= i;
            }

            total_solutions *= (2 * power + 1);
        }

    return total_solutions;
}

All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí