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 1≤N≤109S = 1^2 + 2^2 + cdots + N^2, text{với }1 le N le 10^9
S=12+22+⋯+N2,với 1≤N≤109

Đố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 $i$ với $i$ từ $1$ tới $N,$ rồi gán $S=S+(i\ast i)$ là xong! Nhưng sự thật có đơn giản như vậy? Ta để ý thấy giới hạn $N$ của bài toán lên đến 109,10^9,109, do đó nếu thực hiện vòng lặp từ $1$ tới $N$ 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 $S$ là N(N+1)(2N+1)6,frac{N(N+1)(2N+1)}{6},6N(N+1)(2N+1)​, từ đây có thể tính được $S$ 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 $S$ 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 ∀n∈N∗forall n in N^{*}∀n∈N∗ thông qua $3$ bước:

• Bước $1$: Kiểm tra mệnh đề đúng với $n=1$.
• Bước $2$: Giả sử mệnh đề đúng với $n=k\ge 1$ (Gọi là giả thiết quy nạp).
• Bước $3$: Chứng minh mệnh đề đúng với $n=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 $n\ge p$ ($p$ là số tự nhiên) thì thuật toán là:

• Bước $1$: Kiểm tra mệnh đề đúng với $n=p$.
• Bước $2$: Giả sử mệnh đề đúng với $n=k\ge 1$ (giả thiết quy nạp)
• Bước $3$: Cần chứng minh mệnh đề đúng với $n=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,$ viết tắt là $\varphi (N)$ – là số lượng các số nguyên dương không vượt quá $N$ và nguyên tố cùng nhau với $N$. Công thức thường gặp của phi hàm Euler là:

ϕ(N)=N×∏p∣N(1−1p)phi(N) = Ntimesprod_{p|N}(1-frac{1}{p})
ϕ(N)=N×p∣N∏​(1−p1​)

với $p$ là các ước nguyên tố của $N$.

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})O(N​). Bạn đọc hoàn toàn có thể cải tiến độ phức tạp thành $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ể.

intphi_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, $\varphi (N)$ có thể tính nhanh như sau:

• Nếu $N$ là một số nguyên tố: $\varphi (N)=N-1$.
• Nếu N=pkN=p^kN=pk với p là một số nguyên tố: ϕ(N)=pk−1×(p−1)phi(N) = p^{k – 1}times (p – 1)ϕ(N)=pk−1×(p−1).

1.2. Tính phi hàm Euler cho mọi số từ $1$ tới $N$

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⌊piN​⌋ là giá trị phần nguyên của Npi⋅frac{N}{p^i} cdotpiN​⋅

Như vậy, ⌊Npi⌋left lfloor{frac{N}{p^i}} right rfloor⌊piN​⌋ sẽ bằng $0$ với ∀i:pi>Nforall i:p^i > N∀i:pi>N.

Chứng minh: Từ $1$ tới $N,$ cứ $p$ số liên tiếp chắc chắn sẽ có một số chia hết cho $p,$ do đó số lượng số chia hết cho $p$ từ $1$ tới $N$ là ⌊Np⌋left lfloor{frac{N}{p}} right rfloor⌊pN​⌋. Tương tự ta có số lượng số chia hết cho p2,p3,…p^2, p^3,…p2,p3,... lần lượt là ⌊Np2⌋,⌊Np3⌋,…left lfloor{frac{N}{p^2}} right rfloor, left lfloor{frac{N}{p^3}} right rfloor,…⌊p2N​⌋,⌊p3N​⌋,... 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νp​(N!)=⌊pN​⌋+⌊p2N​⌋+⌊p3N​⌋+⋯

Cài đặt:

intlegrende_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(log⁡p(N))O(log_p(N))O(logp​(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 $k$ lớn nhất sao cho $N!$ chia hết cho MkM^kMk với $M$ 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ử $M$ 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}
M=p1r1​​×p2r2​​×⋯pnrn​​

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

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

N!=p1r1′×p2r2′×⋯pnrn′N!=p_1^{r’_1} times p_2^{r’_2} times cdots p_n^{r’_n}
N!=p1r1′​​×p2r2′​​×⋯pnrn′​​

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

k.r1≤r1′;k.r2≤r2′;…;k.rn≤rn′k.r_1 le r’_1; k.r_2 le r’_2;…; k.r_n le r’_n
k.r1​≤r1′​;k.r2​≤r2′​;...;k.rn​≤rn′​

Nói cách khác, νpi(N!)=⌊ri′ri⌋nu_{p_i}(N!)=left lfloor{frac{r’_i}{r_i}} right rfloorνpi​​(N!)=⌊ri​ri′​​⌋. Từ đó suy ra kmax=min⁡⌊νpi(N!)ri⌋;∀i:1≤i≤nk_{max}=minleft lfloor{frac{nu_{p_i}(N!)}{r_i}} right rfloor; forall i: 1 le i le nkmax​=min⌊ri​νpi​​(N!)​⌋;∀i:1≤i≤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.

intlegendre_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!$

Một ứng dụng hay của công thức Legendre là tìm số ước của $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}p1r1​​×p2r2​​×⋯×pnrn​​ 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)(r1​+1).(r2​+1)...(rn​+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ố $p$ trong $N!$, ta có thể áp dụng công thức Legendre như sau:

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

Cài đặt: Giải thuật dưới đây có độ phức tạp tổng quát là $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;}intfactorial_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=1Nfrac{1}{x}+frac{1}{y}=frac{1}{N}x1​+y1​=N1​

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

1x+1y=1Nfrac{1}{x}+frac{1}{y}=frac{1}{N}x1​+y1​=N1​⇔x+yxy=1NLeftrightarrow frac{x+y}{xy}=frac{1}{N}⇔xyx+y​=N1​$\iff xy-N.(x+y)=0$

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

⇔xy−N.(x+y)+N2=N2Leftrightarrow xy-N.(x+y)+N^2=N^2⇔xy−N.(x+y)+N2=N2⇔xy−Nx−Ny+N2=N2Leftrightarrow xy-Nx-Ny+N^2=N^2⇔xy−Nx−Ny+N2=N2⇔x.(y−N)−N.(y−N)=N2Leftrightarrow x.(y-N)-N.(y-N)=N^2⇔x.(y−N)−N.(y−N)=N2⇔(y−N).(x−N)=N2Leftrightarrow (y-N).(x-N)=N^2⇔(y−N).(x−N)=N2

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,N2, vì ứng với một ước $i$ của N2N^2N2 thì sẽ có một ước nữa là Ni,frac{N}{i},iN​, khi đó $(y-N)=i$ và (x−N)=Ni⋅(x-N)=frac{N}{i} cdot(x−N)=iN​⋅

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ố:

intcount_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;}