01. Lý thuyết Số học

Giới thiệu

Lý thuyết số học là một nhánh trong toán học, hiểu được các kiến thức này là nền tảng quan trọng để chúng ta giải được rất nhiều bài toán trong lập trình nhằm giảm bớt quá trình tính toán. Các nội dung chúng ta sẽ thảo luận bao gồm: Số nguyên tố, ước, bội, ước chung lớn nhất, modulo.

Số nguyên tố

Đị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, … 

Kiểm tra số 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  mà k (từ 2 đến căn bậc 2 của N) 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, \sqrt(N)]}:

bool  IsPrime (int N)

{

  if (N==2 || N==3) return true;

  if (N==1 || N%2==0 || N%3==0) return false;

        int k=-1;

  while (k<=int(sqrt(N)))

{ 

         k+=6;

    if (N%k==0 || N% (k+2)==0) break;

}

return k>int(sqrt(N));

}

Kiểm tra nguyên tố theo xác suất

Tham khảo trang 15, SGK chuyên Tin quyển 1 - Hồ Sỹ Đàm

Liệt kê các số nguyên tố trong đoạn [1, N]

Cách 1 - Đơn giản

Cách này chỉ cần duyệt trong đoạn [1,N] rồi lần lượt kiểm tra tính nguyên tố của nó.

void OutPrime(int N)

{

   for(int i = 2; i <= N; i++)

      if(IsPrime(i))

         printf("%d\t", i);

} 

Cách này tuy đơn giản nhưng chạy chậm. Để cải tiến ta cần dùng một số sàng nguyên tố, ví dụ sàng Eratosthene (ngoài ra các bạn có thể tham khảo sáng Atkin, Pritchard, Sundaram)

Cách 2 - Dùng sàng Eratosthene

Đây là một thuật toán rất cổ xưa dùng để liệt kê các số nguyên tố nhỏ hơn số nguyên N cho trước. 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 {\sqrt(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ố.

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);

} 

Độ phức tạp thuật toán là O(NlogN), tuy nhiên cách này khá tốn bộ nhớ.

Mở rộng

Phân tích thừa số nguyên tố với sàng Erathosthane (đọc thêm tại VNOI)

Sàng nguyên tố trên đoạn (đọc thêm tại VNOI)

Nhiệm vụ 1. C11PNUM - Số nguyên tố

Nguồn: SPOJ.com - Problem C11PNUM 

Tóm tắt: 

Cho 2 số nguyên N và K (1 <= N <= 264 - 1, 3 <= K <= 10). 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.

Input

• Dòng đầu là số nguyên T tương ứng với số bộ test (1 <= T <= 15)

• T dòng tiếp theo mỗi dòng là 1 cặp số (N, K) cách nhau 1 dấu cách

Output

• Gồm T dòng là kết quả của T bộ test tương ứng, nếu không tìm được số thỏa mãn in ra -1

Example

Input:

2

100 4

110 3

Output:

-1

105

Nhiệm vụ 2 - C11PRIME - Số nguyên tố 

Nguồn: https://vn.spoj.com/problems/C11PRIME/ 

Tóm tắt:

Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Trong một buổi dã ngoại của trường, bất ngờ TMB bị thầy giáo đố một câu như sau: “Một số có dạng p^q là lũy thừa cao của một số nguyên tố khi và chỉ khi p là một số nguyên tố và q > 1. Thầy sẽ cho em một số N bất kỳ và em hãy cho biết đó có phải là lũy thừa cao của một số nguyên tố hay không?”. Không phải lúc nào cũng mang theo máy tính bên mình, đây là lúc TMB cần bạn.

Yêu cầu: Cho số N, hãy giúp TMB trả lời câu đố của thầy giáo, nếu N là lũy thừa cao của một số nguyên tố thì in ra 2 số p và q tương ứng, nếu không thì ghi 0.

Giới hạn:

n <= 10^18

Input:

• 1 dòng duy nhất chứa n

Output:

• 1 dòng duy nhất là kết quả

Nhiệm vụ 3 - SPRIME - Số đặc biệt

Nguồn: Tài liệu của hội thảo các trường chuyên duyên hải và đồng bằng Bắc bộ 2018

Link chấm bài: TKNCODER.NET

Tóm tắt:

Nhiệm vụ 4 - TDPRIMES - Printing some primes

Nguồn: https://www.spoj.com/problems/TDPRIMES/en/

Tóm tắt:

Xuất các số nguyên tố nhỏ hơn 10^8, Kết quả xuất lấy dư khi chia cho 100.

Input

There is no input.

Output

To make the problem less output related write out only the 1st, 101st, 201st, ... 1st mod 100.

Example

Input:

Output:

2

547

1229

...

99995257

99996931

99998953

Nhiệm vụ 5 - Strongly Composite 

Nguồn: Codeforce

Tóm tắt:

Một số gọi là hợp số mạnh (strongly composite) nếu như trong số các ước của nó, trừ số 1 ra, số lượng ước là hợp số nhiều hơn số lượng số nguyên tố. Ví dụ 12 có 6 ước: 1, 2, 3, 4, 6, 12. Trừ số 1 ra còn lại 5 ước, có 3 hợp số là 4, 6, 12 nhiều hơn số nguyên tố là 2 và 3, nên ta gọi 12 là hợp số mạnh.

Số 15 có 4 ước: 1, 3, 5, 15. trừ số 1 ra, còn lại 3 ước, trong đó có 2 ước nguyên tố là 3 và 5, chỉ có một ước là hợp số: 15, nên ta gọi 15 không phải là hợp số mạnh.

Bạn được cho trước một dãy n số nguyên a1, a2, ..., aN (ai >1). Nhiệm vụ của bạn là xây dựng dãy b theo quy tắc sau đây:

Tích các phần tử của a bằng tích các phần tử của b. a1*a2*...*an = b1*b2*bk

Tất cả các phần tử của b đều là hợp số mạnh

Kích thước k của b là lớn nhất có thể

Input:

Mỗi test chứa nhiều t testcase ( t<=1000), trong mỗi test sẽ có:

• Dòng đầu tiên chứa số nguyên n là kích thước của dãy a (n<=1000)

• Dòng tiếp theo chứa n số nguyên từ a1 đến an

• Bộ dữ liệu luôn đảm bảo tổng các n của t testcase không vượt quá 1000.

Output:

Mỗi testcase in ra số nguyên k, hoặc 0 nếu không thể sinh ra dãy b thỏa điều kiện.

Nhiệm vụ 6 - VECTAR8 - Primal Fear

Nguồn: https://www.spoj.com/problems/VECTAR8/en/

Tóm tắt:

Changu and Mangu rất sợ những số nguyên tố mà:

• Không có chứa chữ số 0 bên trong

• Cho dù có bỏ đi bao nhiêu chữ số đầu thì phần còn lại của nó vẫn là số nguyên tố

Bạn được cho cho một số nguyên N, hãy đếm số lượng số nguyên tố không lớn hơn N mà Changu và Mangu sợ.

Input:

• Dòng đầu chứa số nguyên T (T<=10^5) là số lượng testcase

• T dòng sau mỗi dòng chứa một số nguyên N (N<=10^6)

Output:

• T dòng, mỗi dòng là kết quả của một testcase.

Ví dụ:

Input:

3

2

3

4

Output:

1

2

2

Nhiệm vụ 7 - Quả cân (SPOJ)

Nguồn: https://vn.spoj.com/problems/LASCALE/

Tóm tắt:

Một cái cân hai đĩa có các quả cân có khối lượng 3^k (ví dụ 3^0, 3^1, 3^2,.....), mỗi loại chỉ có một quả cân duy nhất. Cho một vật nặng có khối lượng N. vật nặng được đặt vào đĩa bên trái của cái cân. Hãy đưa ra cách cân để cân được vật năng trên (hai bên cân bằng)

Input

- Chứa 1 số nguyên N duy nhất (0 <= N <= 100 000 000)

Output

- Kết quả gồm 2 dòng

- Dòng 1: số A là số quả cân đặt vào đĩa bên trái, theo sau gồm A số là khối lượng của các quả cân theo thứ tự tăng dần

- Dòng 2: số B là số quả cân đặt vào đĩa bên phải, theo sau gồm B số là khối lượng của các quả cân theo thứ tự tăng dần

Ví dụ 1:

Input:

11

Output:

1 1 

2 3 9 

Ví dụ 2:

Input:

42

Output:

3 3 9 27

1 81

Tài liệu tham khảo

1. Sách giáo khoa chuyên Tin quyển 1 - Hồ Sỹ Đàm, NXB GD Việt Nam,  trang 19 đến 22

2. VNOI

3. Hackerearth

4. SPOJ

5. Codeforce

6. Guide to Competitive Programming, second edition, Antti Laaksonen, Springer, page from 156 to 160

7. Tài liệu từ hội thảo khoa học các trường chuyên Khu vực Duyên hải và Đồng bằng Bắc bộ lần thứ XI, tại tỉnh Hưng Yên năm 2018