VẬN DỤNG KIẾN THỨC SỐ HỌC TRONG VIỆC LẬP TRÌNH GIẢI CÁC BÀI TOÁN BẰNG NGÔN NGỮ c++

Ly ́ do cho ̣n đề tài

Số học là một phần quan trọng trong chương trình Toán học từ cấp 2, giúp học sinh làm quen với các khái niệm như dấu hiệu chia hết và cách tìm chữ số tận cùng Việc áp dụng kiến thức số học trong các bài toán Tin học không chỉ giúp tìm ra những thuật toán tối ưu mà còn tạo điều kiện cho học sinh có nền tảng Toán học vững chắc dễ dàng suy luận Điều này không chỉ kích thích niềm đam mê lập trình mà còn hình thành kỹ năng tối ưu hóa thuật toán ngay từ những bước đầu trong quá trình học lập trình.

Trong quá trình giảng dạy và bồi dưỡng học sinh giỏi, chúng tôi nghiên cứu các bài toán Tin học ứng dụng kiến thức số học cơ bản Đề tài “Vận dụng kiến thức Số học trong việc lập trình giải các bài toán bằng ngôn ngữ C++” được đưa ra nhằm cung cấp tài liệu tham khảo hữu ích cho học sinh và giáo viên trong việc học tập và giảng dạy.

Cấu trúc nội dung

Phần 1 Lý thuyết cơ bản

1 Các dấu hiệu chia hết cho các số

Phần 2 Hệ thống các bài tập

Mu ̣c đích nghiên cứu

Trong quá trình nghiên cứu và giảng dạy, chúng tôi nhận thấy rằng việc áp dụng kiến thức số học vào giải quyết một số bài toán mang lại hiệu quả cao Do đó, chúng tôi quyết định viết đề tài này với mục đích khám phá và trình bày những ứng dụng thực tiễn của số học trong giải toán.

- Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng các kiến thức

Số học trong việc lập trình giải một số bài toán

- Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG.

Phương pháp nghiên cứu

Kinh nghiệm bản thân, thảo luận, sưu tầm tài liệu, thử nghiệm thực tế, rút kinh nghiệm từ các tiết dạy trên lớp.

Giới hạn phạm vi nghiên cứu của đề tài

Bài viết này tập trung vào việc nghiên cứu hệ thống bài tập ứng dụng kiến thức số học nhằm tối ưu hóa thuật toán Nó chỉ ra các thuật toán tối ưu trong việc giải quyết các bài toán cụ thể và trình bày cách cài đặt chương trình bằng ngôn ngữ lập trình C++.

Ba đề tài có tiềm năng ứng dụng rộng rãi trong việc giảng dạy và bồi dưỡng học sinh giỏi môn Tin học cho giáo viên và học sinh cấp THCS, THPT trên toàn tỉnh Nghệ An.

Nắm vững kiến thức số học là rất quan trọng, giúp học sinh áp dụng để giải quyết các bài toán cụ thể Bài viết này sẽ trình bày những kiến thức số học cần thiết cùng với hệ thống bài tập mà chúng tôi đã nghiên cứu và áp dụng hiệu quả trong giảng dạy.

Lý thuyết cơ bản

Các dấu hiệu chia hết cho các số

 Các chữ số tận cùng là 0,2,4,6,8 thì chia hết cho 2, hoặc các số chẵn thì chia hết cho 2

 Các số có tổng các chữ số chia hết cho 3 thì số đó chia hết cho 3

 Các số có hai chữ số cuối tạo thành một số chia hết cho 4 thì số đó chia hết cho 4

 Các số có tận cùng là 0 hoặc 5 thì chia hết cho 5,……

Số nguyên tố

a) Định lý cơ bản của số học

Mọi số tự nhiên lớn hơn 1 đều có thể được phân tích một cách duy nhất thành tích của các thừa số nguyên tố, không tính đến thứ tự của các thừa số Điều này có nghĩa là mỗi số tự nhiên n lớn hơn 1 có một cách biểu diễn duy nhất dưới dạng tích các thừa số nguyên tố.

1, có thể viết duy nhất dưới dạng:

Trong đó p p 1 , 2 , ,p k là các số nguyên tố và   1 , 2 , , k là các số tự nhiên nguyên dương

Dựa vào định lý này, ta có thể chứng minh định lý sau:

 Mọi hợp số phải có ước nguyên tố nhỏ hơn hay bằng căn bậc hai của nó

Giả sử n (1 < a, b < n) Nếu cả a và b đều lớn hơn căn bậc hai của n, thì sẽ dẫn đến mâu thuẫn n > n Do đó, phải tồn tại ít nhất một thừa số không vượt quá căn bậc hai của n, hay có một ước nguyên tố không lớn hơn căn bậc hai của n.

 Số tất cả các ước tự nhiên của n là ( 1 1)( 2 1) ( k 1) b) Một vài tính chất liên quan đến số nguyên tố:

 Ước tự nhiên khác 1 nhỏ nhất của một số tự nhiên là số nguyên tố

 Nếu tích của nhiều số chia hết cho một số nguyên tố p thì có ít nhất một thừa số chia hết cho p

 Ước số nguyên dương bé nhất khác 1 của một hợp số a là một số nguyên tố không vượt quá a,…

Đồng dư thức là một khái niệm quan trọng trong lý thuyết số, với các tính chất đặc trưng giúp giải quyết nhiều bài toán toán học Định lý Ferma, đặc biệt là định lý Ferma nhỏ, đóng vai trò quan trọng trong việc hiểu rõ hơn về đồng dư thức Định lý Ferma nhỏ khẳng định rằng nếu p là một số nguyên tố và a là một số nguyên không chia hết cho p, thì a^(p-1) ≡ 1 (mod p) Tổng quát hóa của định lý Ferma mở rộng các ứng dụng của khái niệm này trong các lĩnh vực khác nhau của toán học.

Nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, a p -a sẽ chia hết cho p Nghĩa là a p a(mod )p

Một dạng tổng quát của định lý Fermat cho biết rằng nếu p là số nguyên tố và m, n là các số nguyên dương thỏa mãn m ≡ n (mod p - 1), thì với mọi số nguyên a, m ≡ a n (mod p) Định lý Fermat cũng được mở rộng bởi Định lý Euler, trong đó cho rằng với bất kỳ modulo n nào và số nguyên a là số nguyên tố cùng nhau với n, ta sẽ có những kết quả tương tự.

Hàm phi Euler, ký hiệu là (n), được sử dụng để đếm số lượng các số nguyên từ 1 đến n mà nguyên tố cùng nhau với n Hàm này là một tổng quát hóa của định lý nhỏ Fermat; cụ thể, nếu n là một số nguyên tố p, thì (p) = p - 1.

Bài tập

Cho 4 số nguyên dương a, b, c và d Đếm số lượng số thuộc đoạn [a, b] chia hết cho cả c và d (a ≤ b)

Input: Gồm một dòng duy nhất chứa 4 số nguyên dương a, b, c, d

Output: Đưa ra kết quả bài toán

 60% số test còn lại có a, b, c, d ≤ 10 9

Với a, b, c, d ≤ 10 6 , ta chỉ việc cho một biến i chạy từ a -> b và đếm số lượng số chia hết cho cả c và d là được

Đối với các số a, b, c, d ≤ 10^9, việc chia hết cho cả c và d thực chất là chia hết cho bội chung nhỏ nhất (BCNN) của c và d Do đó, công thức tính toán sẽ dựa trên BCNN của hai số này.

4 long long lcm(long long X, long long Y)

Cho dãy số nguyên dương a 1 , a 2 , … , a n và số nguyên K Hãy đếm xem có bao nhiêu cặp chỉ số i, j thỏa mãn: o 1  i < j  n o Bội chung nhỏ nhất của a i và a j lớn hơn K

Input: o Dòng thứ nhất ghi hai số nguyên n và K (1 < n  1000; 0  K  10 9 ) o Dòng thứ hai ghi n số nguyên dương a 1 , a 2 , … , a n (a i  10 4 )

Output: Gồm một số duy nhất là số cặp chỉ số tìm được

Xây dựng hàm tính BCNN Sau đó, đọc dữ liệu vào một mảng a, ta tiến hành duyệt mảng và cập nhật: if (lcm(a[i],a[j]) >=k) res++

5 li lcm(li a, li b) { return a / gcd(a, b) * b; }

Cho 3 số nguyên dương a, b, c Tính a b mod c

Input: Gồm một dòng duy nhất chứa 3 số nguyên dương a, b và c

Output: In ra kết quả bài toán

 40% số test còn lại có a, b, c ≤ 10 9

Với a, b, c ≤ 10 Ta cần một biến ans = 1, sau đó chạy một biến i từ 1 → b và tăng biến ans = ans * a, kết quả chính là (ans % c)

Với a, b, c ≤ 10 6 Một tính chất toán học đúng đắn đó là :

Đầu tiên, gán biến ans = 1 Sau đó, sử dụng biến i chạy từ 1 đến b, trong mỗi lần lặp, cập nhật ans bằng cách tính (ans*a) % c Việc thực hiện phép modulo c ngay lập tức giúp giữ giá trị của ans luôn nhỏ hơn c, từ đó ngăn chặn tình trạng tràn số.

Cả 2 trường hợp trên độ phức tạp thuật toán là O(b)

Với a, b, c ≤ 10 9 Ở đây ta sẽ dùng đến thuật toán chia để trị, ta có tính chất:

 a b % c = (a b/2 % c) (a b/2 % c) a nếu b lẻ gọi F(a, b, c) = a b % c sẽ gọi đến hàm F(a, b/2, c) Do đó ta có thể dùng đệ qui để tính (a b % c) với đpt O(log(b))

4 long long pw(long long A,long long B,long long C)

Cho hai số nguyên dương a và b Tìm chữ số tận cùng của a b

 Dòng thứ nhất chứa số nguyên dương a

 Dòng thứ hai chứa số nguyên dương b

Output: In ra kết quả bài toán

 10% số test còn lại có a, b ≤ 10 100000

Với a, b ≤ 10 Ta chạy một biến i từ 1 → b để tính ans = (ans * a) Sau đó xem số đó có chữ số tận cùng là bao nhiêu → O(b)

Với a, b ≤ 10 6 Nhận thấy ta cần tính (a b % 10) Chạy một biến i từ 1 → b sau đó gán lại ans = (ans * a) % 10 Kết quả chính là ans → O(b)

Để tính (a b % 10) với a, b ≤ 10^9, ta áp dụng phương pháp chia để trị với độ phức tạp O(log(b)) Đối với a, b ≤ 10^18, trước tiên cần gán lại a = (a % 10) để tránh tràn số, sau đó sử dụng phương pháp chia để trị để thực hiện phép tính.

Với a, b ≤ 10^100000, chúng ta có thể đọc hai số a và b dưới dạng chuỗi Để giải quyết bài toán, chỉ cần lấy chữ số cuối cùng của a (%10) và hai chữ số cuối cùng của b Tất cả các số nguyên dương khi được nâng lên mũ 4 sẽ có chữ số tận cùng là 0, 1, 5 hoặc 6 Những số có chữ số tận cùng là 0, 1, 5, 6 sẽ giữ nguyên chữ số tận cùng không đổi, bất kể số mũ là bao nhiêu Nhờ vào tính chất này, việc tính toán trở nên đơn giản hơn, với độ phức tạp rất nhỏ do chỉ cần xem xét hai chữ số cuối cùng của b.

5 long long pw(long long A,long long B,long long C){

Cho hai số nguyên dương a và b Đếm số lượng số nguyên tố thuộc đoạn [a, b]

Input: Gồm một dòng duy nhất chứa 2 số nguyên dương a và b (a ≤ b) Output: Đưa ra số lượng số nguyên tố

 30% số test còn lại có a, b ≤ 10 7

Để xác định số nguyên tố trong khoảng từ a đến b (với a, b ≤ 1000), ta có thể sử dụng một vòng lặp với biến i chạy từ a đến b Mỗi lần kiểm tra xem i có phải là số nguyên tố hay không sẽ tốn O(i) thời gian Do đó, trong trường hợp xấu nhất, độ phức tạp của thuật toán sẽ là O((b – a) * b).

Để xác định các số nguyên tố trong khoảng từ a đến b, với a, b ≤ 10^5, ta có thể sử dụng một biến i chạy từ a đến b Mỗi số i sẽ được kiểm tra tính nguyên tố với độ phức tạp cải tiến là O(√𝑖) Do đó, độ phức tạp trong trường hợp xấu nhất của bài toán này sẽ là O((b - a)√𝑏).

Với a, b ≤ 10^7, chúng ta áp dụng kiến thức về sàng nguyên tố để xây dựng một sàng nguyên tố với độ phức tạp O(10^7) Sau đó, chúng ta có thể kiểm tra tính nguyên tố của một số với độ phức tạp O(1) Như vậy, độ phức tạp tổng thể của bài toán được xác định.

9 for(int i=2;i*i