Số học 2

Chuyên đề Số học 2: Khám phá nguyên tố, ước số và ứng dụng. Bài viết cung cấp kiến thức toán học cơ bản và nâng cao, cùng bài tập vận dụng hữu ích.

• Người hướng dẫn: Nguyễn Tiến Thành
• Trường học: Trường Thpt Chuyên Thái Bình
• Chuyên ngành: Số Học
• Đề tài: Số Nguyên Tố, Ước Số, Bội Số, Số Fibonacci, Số Catalan, Xử Lí Số Nguyên Lớn
• Loại tài liệu: Chuyên đề
• Năm xuất bản: 2019 - 2020
• Địa điểm: Thái Bình

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHUYÊN ĐỀ CÁC BÀI TOÁN SỐ HỌC
• 1.1. Số nguyên tố
• 1.1.1. Định nghĩa
• 1.1.2. Kiểm tra tính nguyên tố theo định nghĩa
• 1.1.3. Kiểm tra số nguyên tố theo xác suất
• 1.1.4. Liệt kê các số nguyên tố trong đoạn [1,N]
• 1.1.5. Sử dụng sàng số nguyên tố sàng Eratosthene
• 1.2. ƯỚC SỐ, BỘI SỐ
• 1.2.1. Số các ước của một số
• 1.2.2. Ước chung lớn nhất của hai số
• 1.2.3. Bội chung nhỏ nhất của hai số
• 1.3. Dãy số Fibonacci
• 1.4. Dãy số CATALAN
• 1.5. Xử lí số nguyên lớn
• 1.5.1. Cộng 2 số nguyên lớn
• 1.5.2. Trừ 2 số nguyên lớn (Trừ số lớn cho số bé)
• 1.5.3. Nhân một số nguyên lớn với một nguyên số nhỏ
• 1.5.4. Nhân 2 số nguyên lớn
• 1.5.5. Chia số nguyên lớn cho số nguyên nhỏ
• 1.5.6. Chia hai số nguyên lớn
• 2. MỘT SỐ BÀI TẬP ÁP DỤNG
• 2.1. Bài 1. C11PNUM - Số nguyên tố.com/problems/C11PNUM/
• 2.2. Bài 2. C11PRIME - Số nguyên tố (Nguồn SPOJ) https://vn.com/problems/C11PRIME/
• 2.3. Bài 3. Số đặc biệt
• 2.4. Bài 4. PTIT017J - ACM PTIT 2017 J - Số các số không chia hết (Nguồn SPOJ) http://www.com/PTIT/problems/PTIT017J/
• 2.5. Bài 5. Bội chung nhỏ nhất
• 2.6. Bài 6. PTIT016A - ACM PTIT 2016 A - Bội số chung nhỏ nhất (Nguồn SPOJ) https://www.com/PTIT/problems/PTIT016A/

Tóm tắt

I. Số Nguyên Tố và Hợp Số Tổng Quan Ứng Dụng Chuyên Đề

Chuyên đề số học này tập trung vào các khái niệm cơ bản nhưng quan trọng về số nguyên tố và hợp số, đồng thời đi sâu vào các ứng dụng thực tế của chúng. Từ định nghĩa, cách kiểm tra tính nguyên tố, đến thuật toán sàng Eratosthenes, chuyên đề này cung cấp một nền tảng vững chắc cho việc giải quyết các bài toán số học phức tạp. Khám phá những bí mật ẩn sau những con số, từ những viên gạch cơ bản của số học đến những cấu trúc toán học tinh tế. Bài viết này không chỉ giới thiệu lý thuyết mà còn chú trọng vào việc áp dụng kiến thức vào giải quyết các bài toán số học. Ta đi từ những khái niệm như số nguyên tố, ước số, bội số đến những thuật toán hiệu quả như thuật toán Euclid để tìm ước chung lớn nhất và bội chung nhỏ nhất. Chuyên đề này không chỉ dành cho học sinh giỏi toán mà còn hữu ích cho bất kỳ ai muốn nâng cao khả năng tư duy logic và giải quyết vấn đề. Theo tài liệu gốc, "Trong nhiều bài toán Tin học, việc vận dụng kiến thức số học giúp đưa ra được những thuật toán tối ưu hơn."

1.1. Định nghĩa và tính chất cơ bản của số nguyên tố

Một số nguyên tố là một số tự nhiên lớn hơn 1 chỉ có hai ước số duy nhất là 1 và chính nó. Các số nguyên tố đóng vai trò quan trọng trong lý thuyết số vì chúng là các "viên gạch" xây dựng nên mọi số tự nhiên khác (ngoại trừ 1). Hợp số, ngược lại, là số tự nhiên lớn hơn 1 có nhiều hơn hai ước số. Việc hiểu rõ định nghĩa và tính chất của số nguyên tố là bước đầu tiên để khám phá thế giới số học.

Số học modulo cũng là một khái niệm liên quan, đặc biệt trong việc kiểm tra tính nguyên tố và giải các phương trình đồng dư. Định lý Fermat nhỏ, ví dụ, cung cấp một phương pháp kiểm tra tính nguyên tố dựa trên số học modulo. Ví dụ: Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23...

1.2. Các phương pháp kiểm tra tính nguyên tố hiệu quả

Kiểm tra tính nguyên tố là một bài toán cơ bản trong số học. Phương pháp đơn giản nhất là thử chia số cần kiểm tra cho tất cả các số từ 2 đến căn bậc hai của nó. Nếu không chia hết cho số nào trong khoảng này, thì số đó là số nguyên tố. Tuy nhiên, phương pháp này không hiệu quả với các số lớn. Các phương pháp nâng cao hơn bao gồm kiểm tra theo xác suất (ví dụ, kiểm tra Miller-Rabin) và sử dụng số học modulo kết hợp với các định lý như định lý Fermat nhỏ. Theo tài liệu, có thể "Cải tiến kiểm tra tính nguyên tố của số N bằng cách kiểm tra xem N có chia hết cho số 2, số 3 và các số có dạng 6k 1 trong đoạn 5, N  ."

1.3. Sàng Eratosthenes Thuật toán liệt kê số nguyên tố trong phạm vi

Sàng Eratosthenes là một thuật toán cổ điển và hiệu quả để liệt kê tất cả các số nguyên tố nhỏ hơn hoặc bằng một số cho trước. Thuật toán hoạt động bằng cách loại bỏ dần các bội của các số nguyên tố, bắt đầu từ 2. Các số còn lại sau khi loại bỏ hết các bội chính là các số nguyên tố. Ưu điểm của sàng Eratosthenes là đơn giản và dễ cài đặt, đặc biệt hiệu quả khi cần liệt kê nhiều số nguyên tố trong một phạm vi nhất định. Ví dụ, sàng Eratosthenes có thể được sử dụng để tạo ra một bảng các số nguyên tố để sử dụng trong các ứng dụng khác. "void Eratosthene(int N) { int a[1000] = {0}; //Tạo mảng và gán tất cả bằng 0 for(int i = 2; ii <= N;i++) if(!a[i]) //Nếu là số nguyên tố //Duyệt các phần tử là bội số của i for(int j = ii; j <= N; j+=i) a[j]=1; //Đánh dấu các phần tử là bội số. //In các phần tử là số nguyên tố ra màn hình for (int i=2;i<=N;i++) if(!a[i]) printf("%d ",i); }"

II. Ước Số Bội Số và Các Thuật Toán Tìm Ước Chung Lớn Nhất

Ngoài số nguyên tố, ước số và bội số là những khái niệm quan trọng khác trong số học. Việc tìm ước chung lớn nhất (ƯCLN) và bội chung nhỏ nhất (BCNN) của hai hay nhiều số là một bài toán thường gặp, có nhiều ứng dụng trong thực tế. Thuật toán Euclid là một trong những thuật toán hiệu quả nhất để tìm ƯCLN của hai số. Hơn nữa, hiểu về ước số, bội số mở ra nhiều ứng dụng thú vị, từ việc phân tích thừa số nguyên tố đến giải các phương trình Diophantine. Các khái niệm ước chung, bội chung cũng đóng vai trò quan trọng. Tài liệu gốc cho biết "Ước số chung lớn nhất (USCLN) của hai số được tính theo thuật toán Euclid USCLN  a, b   USCLN b,  a mod b   ."

2.1. Số lượng và tổng các ước của một số cho trước

Số lượng và tổng các ước số của một số có thể được tính toán dễ dàng nếu biết phân tích thừa số nguyên tố của số đó. Nếu một số N có thể được phân tích thành N = a^i * b^j * ... * c^k, thì số lượng ước số của N là (i+1)(j+1)...(k+1), và tổng các ước số của N có thể được tính bằng công thức (1+a+a^2+...+a^i)(1+b+b^2+...+b^j)...(1+c+c^2+...+c^k). Ví dụ: Số 12 = 2^2 * 3^1 có (2+1)(1+1) = 6 ước số: 1, 2, 3, 4, 6, 12.

2.2. Thuật toán Euclid Cách tìm ước chung lớn nhất hiệu quả

Thuật toán Euclid là một phương pháp hiệu quả để tìm ước chung lớn nhất (ƯCLN) của hai số nguyên. Thuật toán dựa trên nguyên lý rằng ƯCLN của hai số không thay đổi nếu số lớn hơn được thay thế bằng hiệu của nó với số nhỏ hơn. Quá trình này lặp lại cho đến khi hai số bằng nhau, và số đó chính là ƯCLN. Phiên bản hiệu quả hơn của thuật toán sử dụng phép chia lấy dư thay vì phép trừ. Để có thể sử dụng hàm tìm UCLN trong C++ ta cần thêm thư viện algorithm. Ví dụ: int main(){ int a = 5, b = 9; printf("\ngcd(%d, %d) = %d", a, b, std::__gcd(a,b)); }

2.3. Mối liên hệ giữa ước chung lớn nhất và bội chung nhỏ nhất

Ước chung lớn nhất (ƯCLN) và bội chung nhỏ nhất (BCNN) có mối quan hệ mật thiết với nhau. Tích của hai số bằng tích của ƯCLN và BCNN của chúng. Công thức này có thể được sử dụng để tính BCNN nếu đã biết ƯCLN, hoặc ngược lại. Công thức tính BCNN (a, b) = (a * b) / ƯCLN (a, b). Theo tài liệu, "ab a BSCNN (a, b)   b USCLN (a, b) USCLN (a, b)"

III. Dãy Fibonacci và Catalan Ứng Dụng Trong Các Bài Toán

Dãy Fibonacci và Catalan là hai dãy số nổi tiếng trong toán học, xuất hiện trong nhiều lĩnh vực khác nhau, từ số học đến tổ hợp và khoa học máy tính. Dãy Fibonacci được định nghĩa bằng công thức truy hồi, trong khi dãy Catalan có công thức tổng quát phức tạp hơn. Cả hai dãy đều có nhiều tính chất thú vị và được áp dụng để giải quyết nhiều bài toán thực tế. Các số Fibonacci là đáp án của các bài toán như Bài toán cổ về sự sinh sản của các cặp thỏ...Dãy số CATALAN được xác định bởi công thức sau: Catalann  C2nn  với n ≥ 0.

3.1. Định nghĩa và các tính chất quan trọng của dãy Fibonacci

Dãy Fibonacci được định nghĩa bằng công thức truy hồi: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n >= 2. Dãy số này có nhiều tính chất thú vị, bao gồm tỷ lệ giữa hai số liên tiếp tiến dần đến tỷ lệ vàng (golden ratio). Dãy Fibonacci xuất hiện trong nhiều lĩnh vực khác nhau, từ tự nhiên (ví dụ, số cánh hoa) đến tài chính (ví dụ, phân tích kỹ thuật). Một số phần tử đầu tiên của dãy số Fibonacci: n 0 1 2 3 4 5 6 … Fibonaccin 0 1 1 2 3 5 8 …

3.2. Ứng dụng của dãy Fibonacci trong các bài toán thực tế

Dãy Fibonacci có nhiều ứng dụng trong thực tế, bao gồm: (1) Bài toán về sự sinh sản của các cặp thỏ, (2) Đếm số cách lát gạch, (3) Tính số đường đi trên lưới, (4) Các bài toán tối ưu hóa, (5) Ứng dụng trong khoa học máy tính như thuật toán tìm kiếm Fibonacci. Các thuật toán dựa trên dãy Fibonacci có thể mang lại hiệu quả cao hơn so với các thuật toán truyền thống trong một số trường hợp nhất định. Ví dụ: đếm số cách xếp n-1 quân domino kích thước 2  1 phủ kín bảng có kích thước 2  (n  1).

3.3. Dãy số Catalan Khái niệm công thức và ứng dụng đa dạng

Dãy Catalan là một dãy số tự nhiên xuất hiện trong nhiều bài toán tổ hợp khác nhau. Số Catalan thứ n, ký hiệu là C_n, có thể được tính bằng công thức C_n = (2n)! / ((n+1)!n!). Dãy Catalan có nhiều ứng dụng, bao gồm: (1) Đếm số cách đặt dấu ngoặc đúng, (2) Đếm số cây nhị phân khác nhau, (3) Đếm số cách chia đa giác thành các tam giác. Một số phần tử đầu tiên của dãy số Catalan là: n 0 1 2 3 4 5 6 … Catalann 1 1 2 5 14 42 132 …

IV. Xử Lý Số Nguyên Lớn Các Thuật Toán Bài Toán Liên Quan

Trong nhiều bài toán số học và mật mã, chúng ta cần xử lý các số nguyên có kích thước rất lớn, vượt quá khả năng biểu diễn của các kiểu dữ liệu số nguyên thông thường. Việc xử lý các số nguyên lớn đòi hỏi các thuật toán đặc biệt để thực hiện các phép toán cộng, trừ, nhân, chia một cách hiệu quả. Xử lý số nguyên lớn bao gồm các phép tính như Cộng 2 số nguyên lớn, Trừ 2 số nguyên lớn, Nhân một số nguyên lớn với một nguyên số nhỏ, Nhân 2 số nguyên lớn và Chia số nguyên lớn cho số nguyên nhỏ. Các bài toán số học liên quan đến số học yêu cầu việc xử lý các phép tính trên các số lớn.

4.1. Thuật toán cộng trừ số nguyên lớn Chi tiết và tối ưu

Thuật toán cộng và trừ số nguyên lớn thường được thực hiện bằng cách biểu diễn số nguyên lớn dưới dạng một mảng các chữ số. Các chữ số được cộng hoặc trừ theo từng cặp, bắt đầu từ hàng đơn vị, và nhớ được chuyển sang hàng kế tiếp nếu cần thiết. Để tối ưu hiệu suất, có thể sử dụng các kỹ thuật như chia nhỏ số thành các khối lớn hơn và sử dụng các phép toán bit để tăng tốc độ tính toán. Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau. Bước 2: Duyệt từ cuối hai xâu về đầu xâu...

4.2. Thuật toán nhân chia số nguyên lớn Hiệu quả và phức tạp

Thuật toán nhân và chia số nguyên lớn phức tạp hơn so với cộng và trừ. Thuật toán nhân thường được thực hiện bằng cách nhân từng chữ số của số thứ nhất với toàn bộ số thứ hai, sau đó cộng các kết quả lại với nhau, tương tự như cách nhân tay thông thường. Thuật toán chia có thể được thực hiện bằng cách sử dụng thuật toán chia dài, hoặc bằng cách sử dụng các thuật toán chia nhanh hơn như thuật toán chia Newton. Phân tích thuật toán: Duyệt từ cuối xâu a về đầu xâu. - Tách từng phần tử của xâu a nhân với xâu b...

4.3. Ứng dụng của xử lý số nguyên lớn trong các bài toán mật mã

Xử lý số nguyên lớn đóng vai trò quan trọng trong nhiều hệ thống mật mã hiện đại, chẳng hạn như RSA và ECC. Các hệ thống này dựa trên độ khó của việc phân tích một số lớn thành các thừa số nguyên tố. Khả năng xử lý số nguyên lớn hiệu quả là yếu tố then chốt để đảm bảo tính bảo mật của các hệ thống này. Các phương trình Diophantine sử dụng số học modulo.

V. Bài Tập Ứng Dụng Chuyên Đề Số Học Nguyên Tố Ước Số

Để củng cố kiến thức và rèn luyện kỹ năng giải quyết bài toán số học, chuyên đề này cung cấp một loạt các bài tập ứng dụng, từ cơ bản đến nâng cao. Các bài tập này bao gồm kiểm tra tính nguyên tố, tìm ƯCLN và BCNN, giải phương trình Diophantine, và áp dụng các thuật toán xử lý số nguyên lớn. Việc giải các bài tập này giúp người học hiểu sâu hơn về các khái niệm và kỹ thuật đã học, đồng thời phát triển khả năng tư duy logic và sáng tạo. Các bài tập áp dụng là: C11PNUM - Số nguyên tố, C11PRIME - Số nguyên tố , Số đặc biệt, PTIT017J - ACM PTIT 2017 J - Số các số không chia hết...

5.1. C11PNUM Số nguyên tố Tìm tích K số nguyên tố liên tiếp

Bài toán yêu cầu tìm số nguyên lớn nhất không vượt quá N và là tích của K số nguyên tố liên tiếp. Để giải bài toán này, cần sử dụng thuật toán sàng Eratosthenes để liệt kê các số nguyên tố trong một phạm vi nhất định, sau đó tính các tích K số nguyên tố liên tiếp và tìm số lớn nhất thỏa mãn điều kiện. Bài này đòi hỏi kiến thức về số nguyên tố.

5.2. PTIT017J ACM PTIT 2017 J Số các số không chia hết

Bài toán yêu cầu tìm số lượng các số nhỏ hơn hoặc bằng N không chia hết cho bất kỳ số nào trong một tập hợp các số cho trước. Để giải bài toán này, cần sử dụng nguyên lý bù trừ. Đầu tiên, tính số lượng các số chia hết cho từng số trong tập hợp, sau đó tính số lượng các số chia hết cho các cặp số, các bộ ba số, v.v. Cuối cùng, áp dụng công thức bù trừ để tính số lượng các số không chia hết cho bất kỳ số nào. Bài này đòi hỏi kiến thức về toán rời rạc.

5.3. CATALAN Dãy số Catalan Tìm thứ tự và dãy số tương ứng

Bài toán yêu cầu tìm thứ tự của một dãy Catalan cho trước, hoặc tìm dãy Catalan có thứ tự cho trước. Để giải bài toán này, cần hiểu rõ về cấu trúc của dãy Catalan và sử dụng các thuật toán đệ quy hoặc quy hoạch động. Nếu gọi A[i,j] là giá trị lớn nhất của BSCNN khi phân tích i thành tổng của j số tự nhiên...

VI. Hướng Nghiên Cứu Phát Triển Chuyên Đề Số Học Ước Số

Chuyên đề số học này cung cấp một nền tảng vững chắc cho việc nghiên cứu và phát triển các lĩnh vực liên quan. Các hướng nghiên cứu tiềm năng bao gồm: (1) Phát triển các thuật toán hiệu quả hơn để kiểm tra tính nguyên tố và phân tích thừa số nguyên tố, (2) Nghiên cứu các tính chất mới của các dãy số đặc biệt như Fibonacci và Catalan, (3) Áp dụng số học vào các lĩnh vực mới như mật mã học và khoa học dữ liệu.

6.1. Các bài toán mở và hướng nghiên cứu mới trong lý thuyết số

Lý thuyết số là một lĩnh vực rộng lớn và phức tạp, với nhiều bài toán mở chưa được giải quyết. Các bài toán này bao gồm giả thuyết Riemann, bài toán Goldbach, và bài toán về sự tồn tại của vô số cặp số nguyên tố sinh đôi. Việc giải quyết các bài toán này đòi hỏi sự kết hợp giữa kiến thức lý thuyết sâu rộng và kỹ năng giải quyết vấn đề sáng tạo.

6.2. Ứng dụng của số học trong mật mã học và an toàn thông tin

Số học đóng vai trò then chốt trong mật mã học và an toàn thông tin. Các hệ thống mật mã hiện đại dựa trên độ khó của các bài toán số học, chẳng hạn như phân tích thừa số nguyên tố và bài toán logarit rời rạc. Việc nghiên cứu và phát triển các thuật toán số học mới có thể dẫn đến các hệ thống mật mã an toàn hơn và hiệu quả hơn.

6.3. Kết nối giữa số học và các lĩnh vực toán học khác

Số học có mối liên hệ mật thiết với nhiều lĩnh vực toán học khác, chẳng hạn như đại số, hình học và giải tích. Các khái niệm và kỹ thuật từ số học có thể được áp dụng để giải quyết các bài toán trong các lĩnh vực này, và ngược lại. Việc khám phá các kết nối này có thể dẫn đến những khám phá toán học mới và thú vị.

Nội dung chính

Tổng quan về giáo trình

Tài liệu "Chuyên đề: Các bài toán số học" (Chuyên đề số học 2: Nguyên tố, Ước số & Ứng dụng) do tác giả Nguyễn Tiến Thành, giáo viên Trường THPT Chuyên Thái Bình biên soạn trong năm học 2019 - 2020. Trong chương trình đào tạo Tin học chuyên sâu và Khoa học Máy tính, các thuật toán số học giữ vai trò nền tảng trong việc thiết kế và tối ưu hóa giải thuật. Giáo trình được biên soạn nhằm chuẩn hóa kiến thức toán học rời rạc ứng dụng, phục vụ công tác bồi dưỡng học sinh giỏi môn Tin học và sinh viên ngành Công nghệ thông tin.

Mục tiêu học tập của tài liệu tập trung vào việc trang bị cho người học hệ thống lý thuyết số học cơ sở, nâng cao năng lực phân tích độ phức tạp thuật toán và chuyển đổi mô hình toán học thành mã nguồn lập trình C++. Cấu trúc của giáo trình được tổ chức thành ba phần chính:

1. Phần I: Mở đầu: Trình bày lý do, tính cấp thiết và định hướng phương pháp tiếp cận các bài toán số học trong môn Tin học.
2. Phần II: Nội dung (Trọng tâm): Hệ thống hóa lý thuyết, thuật toán cơ sở, phân tích mã nguồn cài đặt và tuyển tập 12 bài toán áp dụng có hướng dẫn giải chi tiết.
3. Phần III: Một số bài tập tham khảo: Tuyển tập 11 bài toán mở rộng trích xuất từ các kỳ thi học sinh giỏi và hệ thống chấm trực tuyến (Online Judge).

Điểm đặc thù của tài liệu là phương pháp tiếp cận mở, kế thừa và phát triển từ "Tài liệu giáo khoa chuyên Tin quyển 1", kết hợp trực tiếp giữa định lý toán học với thuật toán thực thi trên ngôn ngữ lập trình C++.

---

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Giáo trình bao quát 6 khối kiến thức toán học thuật toán trọng tâm:

1. Số nguyên tố và tính chất đồng dư:

   • Định nghĩa số nguyên tố ($p > 1$ chỉ có 2 ước là $1$ và chính nó).
   • Thuật toán kiểm tra nguyên tố cơ bản $O(\sqrt{N})$ và thuật toán cải tiến dựa trên dạng số $6k \pm 1$ trong đoạn $[5, \sqrt{N}]$.
   • Lý thuyết kiểm tra nguyên tố theo xác suất, định lý Fermat nhỏ ($a^{p} - a \ \vdots \ p$ hay $a^{p-1} \equiv 1 \pmod p$ với $p$ nguyên tố) và Định lý Euler ($a^{\phi(n)} \equiv 1 \pmod n$ với $\gcd(a,n) = 1$, hàm phi Euler $\phi(n)$).
   • Thuật toán liệt kê số nguyên tố: duyệt tuần tự kết hợp hàm kiểm tra và kỹ thuật sàng số nguyên tố Eratosthene (độ phức tạp $O(N \log \log N)$).

2. Ước số và Bội số:

   • Công thức phân tích thừa số nguyên tố: $N = a^i \cdot b^j \dots c^k$.
   • Công thức xác định số lượng ước: $d(N) = (i + 1)(j + 1)\dots(k + 1)$.
   • Công thức tính tổng các ước: $$\sigma(N) = \frac{a^{i+1}-1}{a-1} \cdot \frac{b^{j+1}-1}{b-1} \dots \frac{c^{k+1}-1}{c-1}$$
   • Thuật toán Euclid tìm Ước số chung lớn nhất (USCLN/GCD): $\gcd(a, b) = \gcd(b, a \pmod b)$ cùng hàm std::__gcd(a, b) trong thư viện <algorithm>.
   • Xác định Bội số chung nhỏ nhất (BSCNN/LCM): $$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$

3. Dãy số Fibonacci:

   • Công thức truy hồi: $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ ($n \ge 2$).
   • Mô hình ứng dụng thực tế: Bài toán sinh sản của các cặp thỏ và bài toán tổ hợp đếm số cách xếp $(n-1)$ quân domino kích thước $2 \times 1$ phủ kín bảng $2 \times (n-1)$.
   • Thuật toán tính $F_n$ bằng phương pháp lặp và tối ưu hóa tính toán theo chu kỳ đồng dư modulo $10^9 + 7$.

4. Dãy số Catalan:

   • Công thức xác định: $$C_n = \frac{1}{n+1} C_{2n}^{n} = \frac{(2n)!}{(n+1)!,n!} \quad (n \ge 0)$$
   • Công thức truy hồi: $$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$$
   • Các bài toán mô hình: Đếm số cách đặt $n$ dấu ngoặc mở và $n$ dấu ngoặc đóng đúng đắn; đếm số lượng cây nhị phân có $n+1$ lá; đếm số cách chia đa giác lồi $(n+2)$ đỉnh thành các tam giác bằng các đường chéo không cắt nhau; quy hoạch động di chuyển trên lưới vuông $(n+1) \times (n+1)$.

5. Xử lý số nguyên lớn (Arbitrary-Precision Arithmetic):

   • Phương pháp biểu diễn số lớn dưới dạng chuỗi ký tự (std::string) và mảng ký tự (char[]).
   • Cài đặt các phép toán số học cơ bản: Cộng hai số nguyên lớn (Congxau), trừ số lớn cho số bé (Truxau), nhân số lớn với số nguyên nhỏ (Nhan1so), nhân hai số nguyên lớn (Nhanxau), chia số nguyên lớn cho số nguyên nhỏ (chia_so), chia hai số nguyên lớn lấy thương và dư (Chiaxau).
   • Cài đặt nâng cao: Cấu trúc dữ liệu BigInt dựa trên std::vector<int> với cơ số BASE = 10000 và nạp chồng toán tử (operator overloading: +, -, *, <).

6. Đại số đồng dư và Quy hoạch động ứng dụng:

   • Tính hàm lũy thừa và chuỗi hàm tuyến tính $g_n(x) = f(g_{n-1}(x))$ mod $10^9+7$ sử dụng kỹ thuật lũy thừa nhị phân (power(a, n)) và nghịch đảo modulo thông qua định lý Fermat nhỏ: $$a / b \pmod p \equiv a \cdot b^{p-2} \pmod p$$
   • Mô hình quy hoạch động phân tích số và tối ưu hóa ước chung lớn nhất (bài toán GCDMAX, NUMBER).

Kiến thức nền tảng được xây dựng

• Cơ sở lý thuyết số học: Thiết lập mối quan hệ giữa phân tích nhân tử, cấu trúc nhóm đồng dư modulo và các định lý tổ hợp rời rạc.
• Nguyên lý tối ưu hóa giải thuật: Chuyển đổi các giải thuật duyệt vét cạn $O(N)$ sang các thuật toán có độ phức tạp logarit hoặc gần tuyến tính ($O(\log N)$, $O(N \log \log N)$).
• Mô hình hóa dữ liệu thuật toán: Kỹ thuật sử dụng mảng cộng dồn (prefix sum) kết hợp mảng đánh dấu nguyên tố, cấu trúc bảng phương án quy hoạch động hai chiều $F[i, j]$.

Kỹ năng phát triển

• Kỹ năng lập trình giải thuật: Cài đặt mã nguồn chuẩn C++11/C++14 sử dụng cấu trúc điều khiển, con trỏ, mảng tĩnh, thư viện STL (vector, string, algorithm).
• Kỹ năng phân tích bài toán: Nhận diện dạng toán tổ hợp và quy đổi về công thức nghiệm đại số (Catalan, Fibonacci, nguyên lý bù trừ).
• Kỹ năng xử lý dữ liệu kích thước lớn: Kỹ thuật thao tác mảng nhớ đối với các số nguyên vượt quá giới hạn 64-bit (unsigned long long $\approx 1.8 \times 10^{19}$).

---

Phương pháp giảng dạy và học tập

Phương pháp tiếp cận sư phạm

Giáo trình triển khai phương pháp giảng dạy tích hợp: Lý thuyết nền tảng $\to$ Thuật toán nguyên bản $\to$ Phân tích giới hạn và tối ưu $\to$ Mã nguồn mẫu $\to$ Bài tập thực hành theo subtask.

Cụ thể, đối với mỗi chủ đề:

• Tác giả trình bày định nghĩa toán học chính xác.
• Minh họa thuật toán trực tiếp từ định nghĩa (ví dụ hàm IsPrime duyệt $2 \dots \sqrt{N}$ hoặc hàm OutPrime in số nguyên tố).
• Đánh giá nhược điểm về thời gian chạy của phương pháp thô.
• Đưa ra giải thuật cải tiến (sàng Eratosthene, thuật toán Euclid, chu kỳ mod 6).
• Cung cấp mã nguồn thực thi hoàn chỉnh bằng C++.

Hệ thống bài tập và nghiên cứu tình huống

Tài liệu thiết kế hệ thống bài tập thực hành chia thành hai mức độ rõ rệt:

1. Nhóm bài tập áp dụng có hướng dẫn (12 bài):

   • Kiểm tra và sàng nguyên tố: Bài 1 (C11PNUM - Tích $K$ số nguyên tố liên tiếp), Bài 2 (C11PRIME - Kiểm tra số dạng lũy thừa nguyên tố $p^q$ với $N \le 10^{18}$), Bài 3 (SPRIME - Số đặc biệt với tổng chữ số chia hết cho 5).
   • Toán rời rạc và nguyên lý bù trừ: Bài 4 (PTIT017J - Đếm số lượng số không chia hết cho 5 số nguyên tố cùng nhau với $N < 2^{63}$).
   • Ước số, Bội số và Quy hoạch động: Bài 5 (NUMBER - Phân tích $N$ thành tổng các số tự nhiên có BSCNN lớn nhất), Bài 6 (PTIT016A - Tìm $N$ để $\text{lcm}(A+N, B+N)$ nhỏ nhất), Bài 7 (P144SUMI - Chia đều $n$ xúc xích cho $m$ người bằng thuật toán tham lam), Bài 12 (GCDMAX - Quy hoạch động tìm USCLN lớn nhất của dãy biến đổi $\pm 1$).
   • Dãy số và Số lớn: Bài 8 (P155PROF - Dãy Fibonacci dạng hiệu modulo), Bài 9 (CATALAN - Xác định thứ tự từ điển và khôi phục cấu hình dãy Catalan), Bài 10 (BIGNUM - Cộng, trừ, nhân số lớn 1000 chữ số), Bài 11 (FUNCTION - Tính giá trị hàm lặp tuyến tính modulo $10^9+7$).

2. Nhóm bài tập tham khảo mở rộng (11 bài):

   • Bao gồm các bài toán trích từ đề thi Olympic và Học sinh giỏi Quốc gia: Bài 13 (P161PROA - Số gần nguyên tố có 3 ước), Bài 14 (BLGEN - Chuỗi gen đặc trưng, Đề thi Olympic 30/4/2014 môn Tin học khối 10), Bài 15 (BSCNN của các số từ $1 \dots n$), Bài 16 (FIBVAL - Bản Vanxơ Fibonacci, Đề thi VOI 2012), Bài 17 (P156SUME - Ước chung của chuỗi), Bài 18 (LQDFIBO - Xâu Fibonacci), Bài 19 (NEWJ - Phương trình đồng dư bậc hai), Bài 20 (Biến đổi dãy về 1 bằng phép toán GCD), Bài 21 (P153PROB - Tính tổng tích chập Catalan), Bài 22 (Analyse - Phân tích số nguyên có GCD bằng 1), Bài 23 (Khôi phục số hạng ban đầu của dãy Fibonacci).

Đánh giá và hướng dẫn tự học

• Định dạng dữ liệu chuẩn: Sử dụng tệp văn bản (.INP và .OUT) và luồng chuẩn (cin/cout, scanf/printf) tương thích với các trình chấm tự động.
• Phân tầng Subtask: Các bài tập đều quy định rõ ràng ràng buộc dữ liệu (ví dụ: 20% test $N \le 10^3$, 30% test $N \le 10^6$, 50% test $N \le 10^{18}$) giúp người học tự đánh giá độ phức tạp thuật toán và tối ưu hóa bộ nhớ trước khi nộp bài.

---

Điểm nổi bật và cập nhật

• Tính sư phạm và hệ thống hóa cao: Tài liệu tổng hợp, tinh lọc và sắp xếp kiến thức số học rời rạc thành một chuỗi logic chặt chẽ, lấp đầy khoảng trống giữa lý thuyết toán thuần túy và kỹ năng lập trình thi đấu.
• Tích hợp kho ngữ liệu từ các kỳ thi chuẩn quốc gia và quốc tế: Toàn bộ hệ thống ví dụ và bài tập được tham chiếu trực tiếp từ các kỳ thi học sinh giỏi (Olympic 30/4, VNOI, VOI 2012) và nền tảng SPOJ / ACM PTIT.
• Kỹ thuật cài đặt tối ưu trên C++:
  • Minh họa song song hai phương pháp xử lý số nguyên lớn: xử lý trực tiếp trên chuỗi (std::string) và cấu trúc mảng vector theo cơ số 10000 (BigInt).
  • Ứng dụng kỹ thuật tiền tính toán (Precomputation) kết hợp mảng cộng dồn (Prefix Sum Array) trên mảng sàng nguyên tố để giải quyết bài toán truy vấn đoạn $[L, R]$ trong độ phức tạp $O(1)$.
  • Xử lý chia đồng dư cho số nguyên tố lớn bằng lũy thừa nhanh kết hợp số mũ nghịch đảo $p-2$ theo định lý Fermat nhỏ.

---

Đối tượng sử dụng giáo trình

Đối tượng	Yêu cầu tiên quyết (Prerequisites)	Mục đích sử dụng
Học sinh khối Chuyên Tin THPT	Đã học cú pháp C/C++ cơ bản, vòng lặp, mảng, hàm, toán rời rạc đại cương.	Ôn luyện đội tuyển học sinh giỏi các cấp, thi Olympic 30/4, Duyên hải Bắc Bộ và Học sinh giỏi Quốc gia (VOI).
Sinh viên ngành CNTT / Khoa học Máy tính	Kiến thức về Cấu trúc dữ liệu & Giải thuật, Đại số tuyến tính, Toán rời rạc.	Nắm vững thuật toán số học phục vụ môn Thiết kế và Phân tích Thuật toán, luyện thi ICPC và Competitive Programming.
Giáo viên, Giảng viên chuyên ngành	Nắm vững giải thuật và phương pháp sư phạm Tin học.	Sử dụng làm tài liệu khung để xây dựng giáo án chuyên đề bồi dưỡng thuật toán số học.
Lập trình viên tự học	Khả năng đọc hiểu mã nguồn C++ và tư duy toán học logic.	Tra cứu thuật toán cơ bản, cải thiện kỹ năng tối ưu mã nguồn và phân tích độ phức tạp thời gian/không gian.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng nào?

Tài liệu phù hợp cho học sinh trường THPT Chuyên (chuyên ngành Tin học), sinh viên các ngành Công nghệ thông tin, Khoa học Máy tính, Toán - Tin và các lập trình viên tham gia thi đấu thuật toán (Competitive Programming).

2. Cần trang bị những kiến thức nền tảng nào trước khi tiếp cận?

Người học cần nắm vững cú pháp lập trình C++ cơ bản (vòng lặp, mảng tĩnh/động, kiểu chuỗi, con trỏ, thao tác tệp tin qua freopen) và các kiến thức toán phổ thông về phép chia hết, ước số chung, phân tích nhân tử và tổ hợp cơ bản.

3. Giáo trình này có điểm gì khác biệt so với các tài liệu thuật toán chung?

Tài liệu không phân tích thuật toán một cách trừu tượng mà đi thẳng vào các kỹ thuật số học ứng dụng, cung cấp đầy đủ mã nguồn C++ có thể biên dịch trực tiếp, kèm theo hướng dẫn giải chi tiết cho các bài toán lấy từ hệ thống SPOJ và các kỳ thi thực tế.

4. Phương pháp tự học giáo trình như thế nào để đạt hiệu quả cao?

Người học nên đọc phần định nghĩa và chứng minh công thức, tự phân tích thuật toán thô trước khi xem phần tối ưu, sau đó gõ lại và tự cài đặt mã nguồn mẫu. Tiếp theo, cần giải quyết các bài tập áp dụng và nộp bài trên các hệ thống chấm trực tuyến tương ứng (SPOJ/VNOI) theo đúng ràng buộc thời gian và bộ nhớ.

5. Tài liệu có cung cấp bộ dữ liệu kiểm thử (Test cases) không?

Trong tài liệu, mỗi bài tập đều có bảng ví dụ mẫu (Input/Output), phân tích giới hạn subtask và dẫn kèm các đường dẫn liên kết tải bộ test tham khảo (ví dụ: các tệp nén .rar đính kèm cho bài 3, bài 5, bài 11, bài 12, bài 20).

---

Kết luận

Chuyên đề "Các bài toán số học" của tác giả Nguyễn Tiến Thành cung cấp một hệ thống kiến thức hoàn chỉnh về lý thuyết số ứng dụng trong Tin học. Tài liệu đóng vai trò kết nối giữa cơ sở toán học rời rạc và kỹ năng lập trình thi đấu thực chiến, từ các thuật toán cơ bản về ước số, số nguyên tố đến các cấu trúc toán học nâng cao như Catalan, chu kỳ Fibonacci và xử lý số lớn.

Lộ trình học tập đề xuất:

1. Nắm vững thuật toán kiểm tra số nguyên tố và sàng Eratosthene.
2. Thực hành các phép toán ước chung lớn nhất (Euclid) và công thức phân tích nhân tử.
3. Cài đặt hoàn chỉnh thư viện xử lý số nguyên lớn (BigInt).
4. Triển khai mô hình bài toán quy hoạch động và đếm tổ hợp (Catalan, Fibonacci).
5. Hoàn thành 23 bài tập thực hành trên hệ thống Online Judge.

Trích đoạn nội dung tài liệu

Mở đầu, Nội dung và Kết luận. Trong phần Nội dung (và cũng là phần chính của chuyên đề) chúng tôi đề cập tới các vấn đề chính: Số nguyên tố, Ước số, Bội số, Số Fibonacci, Số Catalan, Xử lí số nguyên lớn,. Do chuyên đề này là các bài toán số học nên kiến thức cơ sở sẽ được ứng dụng trong từng bài tập cụ thể. Về mặt lí thuyết số học có rất nhiều tài liệu đã trình bày, ngay cả trong cuốn tài liệu giáo khoa chuyên Tin quyển 1 đã hệ thống rất cụ thể.

Chuyên đề là sự sưu tầm, chọn lọc, sắp xếp và hệ thống những vấn đề cơ bản của các bài toán số học theo một mạch kiến thức nhất định dựa trên một số nguồn tài liệu đã có. Cùng với đó, chúng tôi có đưa ra những phân tích, đánh giá để làm sáng tỏ cho mỗi vấn đề được đề cập tới. Với cách tiếp cận mở như vậy, hy vọng chuyên đề này sẽ giúp các em học sinh có được một hệ thống những kiến thức cần thiết, các thầy cô giáo có một chuyên đề chuyên môn bổ ích và thiết thực. Số nguyên tố 1.

Định nghĩa Một số tự nhiên p (p>1) là số nguyên tố nếu p có đúng hai ước số là 1 và p. Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, … 1. Kiểm tra tính nguyên tố theo định nghĩa. Ý tưởng chính để kiểm tra số nguyên dương N (N>1) có là số nguyên tố hay không, ta kiểm tra xem có tồn tại số nguyên k (2  k  N ) mà k là ước của N (N chia hết cho k) thì N không phải là số nguyên tố, ngược lại N là số nguyên tố.

bool IsPrime(int N) { if (N < 2) return flase; for(int i = 2; i < sqrt(N); i++) if(N%i==0) return flase; return true; } Tuy nhiên ta thấy cách này không hiệu quả khì thời gian kiểm tra lâu. Cải tiến kiểm tra tính nguyên tố của số N bằng cách kiểm tra xem N có chia hết cho số 2, số 3 và các số có dạng 6k 1 trong đoạn 5, N . Kiểm tra số nguyên tố theo xác suất Các khái niệm, tính chất của đồng dư thức, và định lý cần nhớ như định lý Ferma. Ở đây tôi đề cập đến định lý Ferma nhỏ và tổng quát hóa của định lý Ferma: Định lý Ferma nhỏ Nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, ap-a sẽ chia hết cho p.

Định lý Fermat còn được tổng quát hóa bởi Định lý Euler: với modulo n bất kỳ và số nguyên a bất kỳ là số nguyên tố cùng nhau với n, ta có: a ( n )  1(mod n). Trong đó  (n) là kí hiệu của hàm phi Euler đếm số các số nguyên giữa 1 và n nguyên tố cùng nhau với n. Đây là tổng quát hóa của định lý nhỏ Fermat vì nếu n=p là số nguyên tố thì  ( p)  n  1. Liệt kê các số nguyên tố trong đoạn [1,N].

Thử lần lượt các số m trong đoạn [1,N], rồi kiểm tra tính nguyên tố của m. void OutPrime(int N) { for(int i = 2; i <= N; i++) if(IsPrime(i)) printf("%d\t", i); } Ta thấy: Cách này đơn giản nhưng chạy chậm, để cải tiến có thể sử dụng các tính chất của số nguyên tố để loại trước những số không phải là số nguyên tố và không cần phải kiểm tra trước các số này. Sử dụng sàng số nguyên tố sàng Eratosthene. Giả sử tất cả đều là số nguyên tố, trước tiên xóa bỏ số 1 ra khỏi tập các số nguyên tố.

Số tiếp theo số 1 là số 2, là số nguyên tố, xóa tất cả các bội số của 2 ra khỏi bảng, xét lên 3, loại tất cả các bội số của 3,… thuật toán tiếp tục cho đến khi gặp số nguyên tố lớn hơn n thì dừng lại. Kết thúc quá trình các số chưa bị loại là số nguyên tố. 4 void Eratosthene(int N) { int a[1000] = {0}; //Tạo mảng và gán tất cả bằng 0 for(int i = 2; i*i <= N;i++) if(!a[i]) //Nếu là số nguyên tố //Duyệt các phần tử là bội số của i for(int j = i*i; j <= N; j+=i) a[j]=1; //Đánh dấu các phần tử là bội số. //In các phần tử là số nguyên tố ra màn hình for (int i=2;i<=N;i++) if(!a[i]) printf("%d ",i); } 2.

ƯỚC SỐ, BỘI SỐ 2. Số các ước của một số Giả sử N được phân tích thành thừa số nguyên tố như sau: N  ai  b j .  c k Ước số của N có dạng: a p  b q . Do đó: Số các ước của N là:  i  1   j  1 .

Ví dụ: N  100  22  52 , số các ước của 100 là:  2  1 2  1  9 (các ước của số đó là: 1, 2, 3, 4, 5, 10, 20, 50, 100). Tổng các ước của một số N  ai  b j .  a 1 b 1 c 1 (231  1) (311  1) Ví dụ: Tổng các ước của 24 là:   60 2 1 3 1 2. Ước chung lớn nhất của hai số Ước số chung lớn nhất (USCLN) của hai số được tính theo thuật toán Euclid USCLN  a, b   USCLN b,  a mod b  .

int gcd(int a, int b) { int tmp; while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; } Chú ý: Để có thể sử dụng hàm tìm UCLN trong C++ ta cần thêm thư viện algorithm. Ví dụ: int main(){ int a = 5, b = 9; printf("\ngcd(%d, %d) = %d", a, b, std::__gcd(a,b)); } 2. Bội chung nhỏ nhất của hai số Bội số chung nhỏ nhất (BSCNN) của hai số được tính theo công thức: ab a BSCNN (a, b)   b USCLN (a, b) USCLN (a, b) 6 3. Dãy số Fibonacci Dãy số Fibonacci được xác định bởi các công thức sau:  F0  0   F1  1 F  F  F  n n 1 n  2 với n ≥ 2 Một số phần tử đầu tiên của dãy số Fibonacci: n 0 1 2 3 4 5 6 … Fibonaccin 0 1 1 2 3 5 8 … Số Fibonacci là đáp án của các bài toán: a) Bài toán cổ về sự sinh sản của các cặp thỏ với các giả thiết như sau: - Các con thỏ không bao giờ chết; - Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái); - Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới.

Giả sử từ đầu tháng 1 có một cặp mới thì đến giữa tháng thứ n sẽ có bao nhiêu cặp? b) Đếm số cách xếp n-1 quân domino kích thước 2  1 phủ kín bảng có kích thước 2  (n  1). Hàm tính số Fibonaci thứ n bằng phương pháp lặp sử dụng công thức Fn  Fn1  Fn2 với n  2 và F0  0, F1  1. Dãy số CATALAN Số Catalan được xác định bởi công thức sau: 1 (2n)! Catalann  C2nn  với n ≥ 0. n 1 (n  1)!n ! Một số phần tử đầu tiên của dãy số Catalan là: n 0 1 2 3 4 5 6 … Catalann 1 1 2 5 14 42 132 … Số Catalan là đáp án của các bài toán: a) Có bao nhiêu cách khác nhau đặt n dấu ngoặc mở và n dấu ngoặc đóng đúng đắn? Ví dụ: n=3 ta có 5 cách sau: ((())), (()()), (())(), ()(()), ()()() b) Có bao nhiêu cây nhị phân khác nhau có đúng n+1 lá? Ví dụ: n=3 c) Cho một đa giác lồi (n+2) đỉnh, ta chia thành các tam giác bằng nhau vẽ các đường chéo không cắt nhau trong đa giác.

Hỏi có bao nhiêu cách chia như vậy? 8 Ví dụ: n=4 5. Xử lí số nguyên lớn 5. Cộng 2 số nguyên lớn Phân tích thuật toán - Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau. Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó.

- Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả c=a; + Tách từng phần tử của hai xâu chuyển sang kiểu số; + Tính tổng: tổng = số 1 + số 2 + nhớ (ban đầu nhớ bằng 0); nhớ = tổng / 10; tổng = tổng % 10; + Chuyển đổi giá trị tổng tính được sang ký tự rồi gán vào xâu kết quả. + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’. Chương trình tham khảo string Congxau(string a, string b) { string c; long n1=a. Trừ 2 số nguyên lớn (Trừ số lớn cho số bé) Phân tích thuật toán - Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau.

Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó. - Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả c=a; + Tách từng phần tử của hai xâu chuyển sang kiểu số; + Tính hiệu: hiệu = số 1 - số 2 - mượn (ban đầu mượn bằng 0); Nếu hiệu<0 thì {hiệu=hiệu+10; mượn=1;} Nếu hiệu>0 thì mượn =0; + Chuyển đổi giá trị hiệu tính được sang ký tự rồi gán vào xâu kết quả. + Xử lý xâu kết quả nếu xâu có độ dài lớn hơn 1 mà phần tử đầu tiên của mảng xâu là ‘0’. 10 Chương trình tham khảo string Truxau(string a, string b) { string c=""; long n1=a.

Nhân một số nguyên lớn với một nguyên số nhỏ Phân tích thuật toán - Bước 1: Duyệt từ cuối xâu số lớn về đầu xâu - Bước 2: + Tách từng phần tử của xâu chuyển sang kiểu số và tính tích: tích = số nhỏ * tg + nhớ (tg là số được tách từ xâu số lớn); nhớ = tích /10; Tích = tích % 10; + Chuyển đổi giá trị tích tính được sang ký tự rồi gán vào xâu kết quả. + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’. 11 Chương trình tham khảo string Nhan1so(string a, int k) { string b; long i,Nho=0,Tich; for(i=a. Nhân 2 số nguyên lớn Phân tích thuật toán - Duyệt từ cuối xâu a về đầu xâu.

- Tách từng phần tử của xâu a nhân với xâu b (Thuật toán nhân với số nhỏ). - Cộng liên tiếp các kết quả thu được (lưu ý trước khi cộng 2 xâu thêm ký tự “0” vào sau xâu thứ 2). - Xử lý các ký tự “0” trước xâu sau khi cộng. Chương trình tham khảo string Nhanxau(string a, string b) { string x,Tg1="0",Tg2,c; long i,j=0; 12 for(i=b.length(),j,'0'); j++; c=Congxau(Tg1,Tg2); Tg1=c; } return c; } 5.