Trong lập trình thi đấu, nhiều bài toán tưởng như yêu cầu một thuật toán phức tạp nhưng thực chất có thể được giải quyết rất ngắn gọn nếu nhận ra cấu trúc toán học bên trong. Toán học trong Competitive Programming không chỉ là ghi nhớ công thức. Điều quan trọng hơn là rèn luyện khả năng: - Nhìn dữ kiện và nhận ra quy luật. - Chuyển mô tả bài toán thành biểu thức toán học. - Biến đổi công thức để giảm độ phức tạp. - Chứng minh tính đúng đắn của thuật toán. - Nhận ra khi nào không cần mô phỏng. - Chuyển từ vét cạn sang công thức hoặc thuật toán tối ưu. - Xử lý chính xác các bài toán với số nguyên rất lớn. - Kết hợp toán học với các kỹ thuật thuật toán khác. Lộ trình này được xây dựng theo hướng: **Nền tảng toán học → nhận dạng cấu trúc → biến đổi → công thức → thuật toán → tối ưu → thực chiến.** Mục tiêu cuối cùng không phải là thuộc nhiều công thức mà là hình thành phản xạ: > Khi gặp một bài toán mới, biết phải quan sát đại lượng nào, đặt biến gì, biến đổi ra sao và sử dụng công cụ toán học nào.

Đăng nhập để tham gia lộ trình luyện tập

Lộ trình Toán học cho Lập trình thi đấu

Mục tiêu của lộ trình

Sau khi hoàn thành lộ trình, người học cần có khả năng:

  • Sử dụng thành thạo các phép toán số học trong lập trình.
  • Phân tích tính chia hết, ước, bội và số nguyên tố.
  • Sử dụng gcd⁡\gcd, lcm⁡\operatorname{lcm} và thuật toán Euclid.
  • Phân tích một số thành thừa số nguyên tố.
  • Làm việc với số dư và đồng dư.
  • Sử dụng lũy thừa nhanh.
  • Tính nghịch đảo modulo khi điều kiện cho phép.
  • Hiểu và sử dụng các tổng thường gặp.
  • Nhận dạng cấp số cộng và cấp số nhân.
  • Biến đổi các tổng phức tạp thành công thức đơn giản hơn.
  • Sử dụng kỹ thuật telescoping.
  • Hiểu tổ hợp, hoán vị và nguyên lý đếm.
  • Tính tổ hợp dưới modulo.
  • Sử dụng nguyên lý bù trừ.
  • Sử dụng nguyên lý Dirichlet.
  • Xử lý các bài toán về phương trình nghiệm nguyên.
  • Nhận dạng các quy luật chu kỳ.
  • Sử dụng tính chất của chữ số và biểu diễn số.
  • Làm việc với hệ cơ số và biểu diễn nhị phân.
  • Hiểu các công thức hình học cơ bản phục vụ lập trình thi đấu.
  • Kết hợp toán học với Binary Search, Greedy, Dynamic Programming và các cấu trúc dữ liệu.

Tư duy cốt lõi

Mỗi bài toán toán học trong lập trình thi đấu nên được tiếp cận theo trình tự sau.

Bước 1. Xác định đại lượng cần tìm

Trước tiên phải xác định chính xác:

  • Đề bài cho gì?
  • Cần tính gì?
  • Đại lượng nào thay đổi?
  • Đại lượng nào cố định?
  • Có cần tìm giá trị hay chỉ cần đếm số trường hợp?

Không nên viết chương trình ngay khi chưa mô hình hóa được bài toán.

Bước 2. Thử với dữ liệu nhỏ

Hãy tự tính một vài trường hợp nhỏ.

Ví dụ:

n=1,2,3,4,5n = 1,2,3,4,5

Quan sát:

  • Giá trị tăng như thế nào?
  • Có lặp lại không?
  • Có tạo thành cấp số không?
  • Có đối xứng không?
  • Có phụ thuộc vào chẵn lẻ không?
  • Có phụ thuộc vào n mod kn \bmod k không?

Nhiều công thức trong lập trình thi đấu được phát hiện từ bước này.

Bước 3. Viết biểu thức toán học

Thay vì mô tả bằng lời, hãy cố gắng viết bài toán thành biểu thức.

Ví dụ cần tính:

1+2+3+⋯+n1+2+3+\cdots+n

Nếu mô phỏng trực tiếp thì cần O(n)O(n) phép cộng.

Nhưng:

1+2+3+⋯+n=n(n+1)21+2+3+\cdots+n=\frac{n(n+1)}{2}

Khi đó chỉ cần O(1)O(1).

Đây là một trong những tư duy quan trọng nhất của toán học trong lập trình thi đấu:

Không mô phỏng những gì có thể tính trực tiếp.

Bước 4. Tìm cấu trúc

Một số cấu trúc thường xuất hiện:

  • Chẵn và lẻ.
  • Chia hết.
  • Ước và bội.
  • Số nguyên tố.
  • Chu kỳ.
  • Đồng dư.
  • Tổng.
  • Hiệu.
  • Cấp số.
  • Đối xứng.
  • Tổ hợp.
  • Hoán vị.
  • Giai thừa.
  • Lũy thừa.
  • Biểu diễn nhị phân.
  • Khoảng cách.
  • Tọa độ.
  • Phương trình.
  • Bất phương trình.

Nhận ra đúng cấu trúc thường quan trọng hơn việc nhớ thuật toán.

Bước 5. Biến đổi

Nếu công thức hiện tại vẫn khó tính, hãy tiếp tục biến đổi.

Một tổng:

S=∑i=1nf(i)S=\sum_{i=1}^{n} f(i)

có thể được:

  • Tách thành nhiều tổng.
  • Ghép các hạng tử.
  • Đổi thứ tự tính.
  • Nhóm theo giá trị giống nhau.
  • Chuyển sang Prefix Sum.
  • Chuyển sang công thức đóng.
  • Rút gọn bằng đồng dư.
  • Biến đổi thành bài toán đếm.

Mục tiêu là đưa bài toán về dạng quen thuộc hơn.

Tư duy từ vét cạn đến tối ưu

Trong lộ trình này, nhiều bài toán sẽ được phân tích theo ba mức.

Mức 1. Vét cạn

Xây dựng lời giải trực tiếp theo định nghĩa.

Mục tiêu của bước này là hiểu đúng bài toán.

Ví dụ:

S=1+2+⋯+nS=1+2+\cdots+n

Có thể cộng lần lượt từng số.

Độ phức tạp:

O(n)O(n)

Mức 2. Nhận dạng quy luật

Quan sát các kết quả nhỏ và tìm cấu trúc toán học.

Với:

1+2+⋯+n1+2+\cdots+n

ta ghép:

1+n1+n 2+(n−1)2+(n-1) 3+(n−2)3+(n-2)

Mỗi cặp đều có tổng:

n+1n+1

Từ đó suy ra công thức.

Mức 3. Công thức hoặc thuật toán tối ưu

Ta có:

S=n(n+1)2S=\frac{n(n+1)}{2}

Độ phức tạp giảm từ:

O(n)O(n)

xuống:

O(1)O(1)

Đây chính là cách học xuyên suốt lộ trình:

Vét cạn → quan sát → phát hiện quy luật → chứng minh → công thức → tối ưu.

Các nhóm kiến thức chính

Lộ trình được tổ chức từ nền tảng đến nâng cao.

Giai đoạn 1. Số học nền tảng

Nắm chắc:

  • Phép chia nguyên.
  • Phép chia lấy dư.
  • Chẵn lẻ.
  • Chia hết.
  • Chữ số.
  • Tổng chữ số.
  • Đảo số.
  • Hệ cơ số.
  • Lũy thừa.
  • Căn bậc hai.
  • Làm tròn và sai số.

Đây là nền tảng để học các phần tiếp theo.

Giai đoạn 2. Tổng và biến đổi đại số

Học cách xử lý:

∑i=1ni\sum_{i=1}^{n} i ∑i=1ni2\sum_{i=1}^{n} i^2 ∑i=1ni3\sum_{i=1}^{n} i^3

cùng các dạng:

  • Cấp số cộng.
  • Cấp số nhân.
  • Tổng đoạn.
  • Tổng lồng nhau.
  • Telescoping.
  • Công thức đóng.
  • Biến đổi biểu thức.

Mục tiêu quan trọng nhất của phần này là giảm các vòng lặp không cần thiết.

Giai đoạn 3. Ước, bội và số nguyên tố

Nắm vững:

  • Ước số.
  • Bội số.
  • Số lượng ước.
  • Tổng các ước.
  • Phân tích thừa số nguyên tố.
  • gcd⁡\gcd.
  • lcm⁡\operatorname{lcm}.
  • Thuật toán Euclid.
  • Sàng Eratosthenes.
  • SPF.
  • Linear Sieve.

Đây là một trong những nhóm kiến thức xuất hiện thường xuyên nhất trong bài toán số học.

Giai đoạn 4. Modular Arithmetic

Học các tính chất:

(a+b) mod m(a+b)\bmod m (a−b) mod m(a-b)\bmod m (a⋅b) mod m(a\cdot b)\bmod m ab mod ma^b\bmod m

và các chủ đề:

  • Đồng dư.
  • Lũy thừa nhanh.
  • Chu kỳ modulo.
  • Nghịch đảo modulo.
  • Định lý Fermat nhỏ.
  • Euler Phi.
  • Định lý Euler.
  • Hệ phương trình đồng dư.

Modulo là nền tảng của rất nhiều bài đếm và tổ hợp.

Giai đoạn 5. Tổ hợp và nguyên lý đếm

Nắm chắc:

  • Quy tắc cộng.
  • Quy tắc nhân.
  • Hoán vị.
  • Chỉnh hợp.
  • Tổ hợp.
  • Giai thừa.
  • Tam giác Pascal.
  • Nhị thức Newton.
  • Tổ hợp modulo.
  • Inclusion-Exclusion.
  • Nguyên lý Dirichlet.

Mục tiêu không chỉ là tính:

(nk)\binom{n}{k}

mà còn phải nhận ra khi nào một bài toán thực chất là bài toán đếm tổ hợp.

Giai đoạn 6. Phương trình và số học nâng cao

Học:

  • Phương trình Diophantine.
  • Phương trình:
ax+by=cax+by=c
  • Extended Euclid.
  • Nghiệm nguyên.
  • Đồng dư tuyến tính.
  • Chinese Remainder Theorem.
  • Hàm Euler.
  • Möbius.
  • Các kỹ thuật đếm theo ước.

Đây là bước chuyển từ số học cơ bản sang Number Theory trong lập trình thi đấu.

Giai đoạn 7. Chu kỳ và quy luật

Nhiều bài toán có trạng thái lặp lại.

Nếu:

xi+k=xix_{i+k}=x_i

thì chu kỳ có độ dài kk.

Khi cần tính trạng thái tại thời điểm rất lớn nn, ta thường chỉ cần xét:

n mod kn\bmod k

Tư duy chu kỳ xuất hiện trong:

  • Chữ số cuối.
  • Lũy thừa.
  • Modular Arithmetic.
  • Đồng hồ.
  • Lịch.
  • Trạng thái xoay vòng.
  • Dãy truy hồi.
  • Mô phỏng.

Giai đoạn 8. Hình học cho lập trình thi đấu

Nắm các công cụ cần thiết như:

  • Điểm.
  • Vector.
  • Khoảng cách.
  • Tích vô hướng.
  • Tích có hướng.
  • Diện tích.
  • Định hướng ba điểm.
  • Đường thẳng.
  • Đoạn thẳng.
  • Đường tròn.
  • Khoảng cách Manhattan.
  • Khoảng cách Euclid.

Mục tiêu là đủ nền tảng để tiếp tục học Computational Geometry.

Giai đoạn 9. Kết hợp toán học với thuật toán

Đây là giai đoạn quan trọng nhất.

Một bài toán thực tế thường không thuộc riêng một chuyên đề.

Ví dụ:

Toán học + Binary Search

Tìm giá trị nhỏ nhất xx thỏa mãn một điều kiện toán học.

Toán học + Greedy

Chứng minh lựa chọn tham lam bằng bất đẳng thức hoặc biến đổi.

Toán học + Dynamic Programming

Tìm công thức chuyển trạng thái từ một quan hệ truy hồi.

Toán học + Prefix Sum

Biến tổng nhiều đoạn thành phép trừ hai tổng tiền tố.

Toán học + Number Theory

Xử lý chia hết, ước, bội hoặc modulo.

Khi đạt tới mức này, toán học trở thành một công cụ hỗ trợ trực tiếp cho việc thiết kế thuật toán.

Phương pháp học mỗi chuyên đề

Mỗi phần nên được học theo trình tự:

1. Hiểu khái niệm.

Biết chính xác đối tượng toán học đang xét là gì.

2. Hiểu bản chất.

Không học thuộc công thức một cách máy móc.

3. Tự tính ví dụ nhỏ.

Kiểm tra công thức bằng tay.

4. Viết lời giải vét cạn.

Tạo mốc so sánh.

5. Phân tích độ phức tạp.

Xác định vì sao lời giải chưa đủ nhanh.

6. Tìm quy luật.

Quan sát cấu trúc toán học.

7. Biến đổi và chứng minh.

Giải thích vì sao công thức đúng.

8. Viết thuật toán tối ưu.

Chuyển công thức thành chương trình.

9. Kiểm tra trường hợp biên.

Ví dụ:

n=0n=0 n=1n=1

hoặc giá trị lớn nhất của dữ liệu.

10. Luyện nhiều biến thể.

Không dừng lại sau khi giải được một bài mẫu.

Cách luyện bài

Mỗi dạng bài nên được luyện theo thứ tự:

Nhận biết → áp dụng trực tiếp → biến đổi → kết hợp → tối ưu → bài tổng hợp.

Không nên chỉ luyện các bài sử dụng công thức trực tiếp.

Ví dụ sau khi học gcd⁡\gcd, cần luyện cả:

  • Tính gcd⁡\gcd.
  • Đếm số liên quan đến gcd⁡\gcd.
  • Kiểm tra khả năng chia.
  • Chuẩn hóa tỉ lệ.
  • Bài toán chu kỳ.
  • Bài toán phương trình.
  • Bài toán kết hợp với Binary Search hoặc Number Theory.

Mục tiêu là hình thành khả năng nhận dạng chứ không phải ghi nhớ tên bài.

Quy tắc quan trọng khi làm bài

Khi gặp một bài có yếu tố toán học, hãy tự hỏi:

  • Có thật sự cần mô phỏng không?
  • Có công thức trực tiếp không?
  • Có thể nhóm các giá trị giống nhau không?
  • Có tính chất chia hết nào không?
  • Có thể dùng gcd⁡\gcd hoặc lcm⁡\operatorname{lcm} không?
  • Có chu kỳ không?
  • Có thể xét modulo không?
  • Có thể biến tổng thành Prefix Sum không?
  • Có thể tách tổng không?
  • Có thể đếm phần bù không?
  • Có thể chuyển bài toán thành tổ hợp không?
  • Có đối xứng không?
  • Có thể giảm miền tìm kiếm bằng căn bậc hai không?
  • Có thể tiền xử lý không?
  • Có thể thay vòng lặp bằng công thức không?

Danh sách câu hỏi này cần dần trở thành phản xạ khi đọc đề.

Mục tiêu cuối cùng

Mục tiêu của lộ trình không phải là trở thành người giải toán thuần túy.

Mục tiêu là sử dụng toán học như một công cụ để thiết kế thuật toán.

Người học cần tiến từ:

Biết công thức

đến:

Hiểu công thức

rồi:

Biết chứng minh

tiếp theo:

Biết nhận dạng khi nào sử dụng

và cuối cùng:

Tự biến đổi bài toán để tạo ra công thức mới.

Khi đạt được mức này, nhiều bài toán tưởng như cần hàng triệu hoặc hàng tỷ phép tính có thể được rút gọn thành vài phép toán.

Đó chính là vai trò cốt lõi của toán học trong lập trình thi đấu.

Phần 1. Số học O(1), floor/ceil, parity, đếm đoạn

Mở

Bài toán Tried AC Độ khó
MTHA0000001   Thương và số dư (Quotient and Remainder) 2 2 1
MTHA0000002   Đếm bội trong đoạn đầu (Count Multiples in a Prefix) 3 2 1
MTHA0000003   Đếm bội trong một đoạn (Count Multiples in an Interval) 4 1 1
MTHA0000004   Đếm số không chia hết (Count Non-Multiples) 3 2 1
MTHA0000005   Đóng thùng tối thiểu (Minimum Number of Boxes) 1 1 1
MTHA0000006   Chuyến xe cuối (The Last Bus Trip) 2 2 1
MTHA0000007   Chia nhóm (Forming Groups) 2 2 1
MTHA0000008   Trang và vị trí (Page and Position) 1 1 1
MTHA0000009   Ghế vòng tròn (Circular Seats) 2 1 1
MTHA0000010   Lịch trực luân phiên (Rotating Duty Schedule) 1 1 1
MTHA0000011   Số có số dư cho trước (Numbers with a Given Remainder) 0 0 1
MTHA0000012   Mốc bảo dưỡng (Maintenance Milestones) 0 0 1
MTHA0000013   Vạch chia cuối cùng (The Last Major Mark) 1 1 1
MTHA0000014   Thời điểm tín hiệu kế tiếp (Next Signal Time) 0 0 1
MTHA0000015   Phân phối theo vòng (Circular Distribution) 1 1 1
MTH000000001   Nghịch lý điểm trung bình (Paradox With Averages) 2 1 1
MTH000000002   Nghịch lý điểm trung bình - bản khó 1 1 1
MTH000000003   Quân tượng (Bishops) 3 2 1
MTH000000004   Các đường cắt (Crne) 1 1 1
MTH000000005   Lấy hai viên đá (Take Two Stones) 5 2 1
MTH000000006   Bàn cờ (Chessboard) 1 1 1
MTH00000007   Sắp xếp nổi bọt (Bubble Sort) 1 1 1
MTH000000008   Tên trộm may mắn (Lucky Thief) 3 2 1
MTH000000009   Hợp kim (Alloys) 1 1 1
MTH000000010   Thử thách Chanukah (Chanukah Challenge) 1 1 1
MTH000000011   Limbo - Phần 1 (Limbo: Part 1) 1 1 1
MTH000000012   Paul Eigon (Paul Eigon) 1 1 1
MTH000000013   Sản xuất tuần tự (Sequential Manufacturing) 1 1 1
MTH000000014   Khẩu phần Soylent (Soylent) 1 1 1
MTH000000015   Ba loại tổng (Sum Kind of Problem) 5 4 1
MTH000000017   Bật đèn, tắt đèn (Light, more light) 1 1 2
MTH000000018   Khách sạn vô hạn phòng (The Hotel with Infinite Rooms) 1 1 2
MTH000000019   Vùng đất công lý (The Land of Justice) 1 1 1
MTH000000020   Hàm f91 (f91) 0 0 1
MTH000000021   Trở lại toán trung cấp (Back to Intermediate Math) 0 0 2
MTH000000022   Loại bỏ lá bài II (Throwing Cards Away II) 0 0 2
MTH000000023   Nỗ lực ít nhất có thể (The Least Possible Effort) 0 0 2
MTH000000024   Tam đẳng cấu (Tri-Isomorphism) 0 0 3
MTH000000025   Số chính phương rất lớn (Very Big Perfect Squares) 0 0 3
MTH000000026   Ba gia đình (Three Families) 3 0 2
MTH000000027   Tiệc trà điên rồ (Crazy Tea Party) 0 0 2

Phần 100. Tổng hợp

Mở

Bài toán Tried AC Độ khó
CT0000061   Đếm số chính phương trong đoạn (Count Perfect Squares in an Interval) 2 1 1
CT0000062   Bình phương hoặc lập phương (Square or Cube) 1 1 2
CT0000063   Nhiều truy vấn đếm số chính phương (Multiple Perfect-Square Count Queries) 2 1 2
CT0000064   Số chính phương gần nhất - EP1 (Nearest Perfect Square - EP1) 0 0 1
CT0000065   Đếm căn theo lớp dư - EP1 (Counting Square Roots by Residue Class - EP1) 0 0 1
CT0000066   Phân tầng theo nhiều khoảng - EP1 (Layer Selection with Multiple Intervals - EP1) 0 0 1
 
Người tham gia
9
Tạo bởi
  1. Danh sách tác vụ
  1. Language
  2. Chế độ cũ
  3. Giao diện
  3. Worker 0, 41ms
  4. Powered by Hydro v5.0.4 Community