Chuyên đề Một số bài toán về số

Nội dung tài liệu: Chuyên đề Một số bài toán về số

1. MỤC LỤC Phần thứ nhất ........................................................................................................................ 2 Phần I. Mở đầu ...................................................................................................................... 2 I. LÝ DO CHỌN ĐỀ TÀI ..................................................................................................... 2 II. ĐỐI TƯỢNG NGHIÊN CỨU ......................................................................................... 2 III. MỤC ĐÍCH NGHIÊN CỨU, ĐÓNG GÓP MỚI CỦA CHUYÊN ĐỀ .................... 2 IV. PHƯƠNG PHÁP NGHIÊN CỨU ................................................................................. 3 V. CẤU TRÚC CỦA CHUYÊN ĐỀ ................................................................................... 3 Phần thứ hai ........................................................................................................................... 4 NỘI DUNG CHUYÊN ĐỀ ................................................................................................... 4 Chương 1. Các thuật toán số học ...................................................................................... 4 I. Số nguyên tố ........................................................................................................................ 4 II.Ước số bội số ....................................................................................................................... 7 III. Số Fibonacci ................................................................................................................... 10 IV. Số Catalan ....................................................................................................................... 13 Chương 2: một số bài toán về số .................................................................................... 16 I. Bài tập có hướng dẫn ........................................................................................................ 16 Bài 1. Bài toán số nguyên tố tương đương ........................................................................ 16 Bài 2. Bài toán FIBOK, tên bài FIBOK ............................................................................. 17 Bài 3. Bài toán Mưu sĩ và nhà vua, tên bài GOLD .......................................................... 19 Bài 4. Bài toán tìm số nguyên k lớn nhất, tên bài TIMK ................................................. 21 Bài 5. Bài toán Phần tử chung, tên bài - Ptc ...................................................................... 23 Bài 6. Số chính phương – SQRNUM.* ............................................................................. 24 Bài 7. Bài toán Chữ số cuối cùng của N!, tên bài OTHER ............................................. 26 Bài 8. Bài toán Tập S và N đoạn số nguyên, tên bài Sets ................................................ 29 Bài 9. Bài toán Counts the permutation! – countper.* ..................................................... 31 II. Bài tập tham khảo ........................................................................................................... 32 Bài 1. C11PRIME - Số nguyên tố ............................................................................... 32 Bài 2. PTIT124F - Vòng số nguyên tố ........................................................................ 33 Bài 3. SSAM019J - ƯỚC SỐ CHUNG LỚN NHẤT .................................................. 34 Bài 4. CPPPRI12 - PRIME 12 ..................................................................................... 34 Bài 5. MMOD29 - CALCULATE POW(2004,X) MOD 29 ....................................... 35 Phần thứ ba .......................................................................................................................... 36 KẾT LUẬN ........................................................................................................................... 36 TÀI LIỆU THAM KHẢO ................................................................................................... 37
2. Chuyên đề: Một số bài toán về số Phần thứ nhất Phần I. Mở đầu I. LÝ DO CHỌN ĐỀ TÀI Số học có liên quan gì đến lập trình? Khi nói đến lập trình trong Tin học chính là một sự kết hợp hoàn hảo giữa toán học và tin họ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. Mặt khác, những bài toán Tin học có sự vận dụng kiến thức số học cơ bản, đòi hỏi sự cài đặt không quá phức tạp và các em có nền tảng Toán học tốt có thể dễ dàng suy luận được. Từ đó kích thích niềm yêu thích của các em trong việc lập trình. Các thuật toán số học trong tin học là nội dung kiến thức khá quan trọng và được sử dụng nhiều trong thiết kế thuật toán. Tuy nhiên, trong quá trình giảng dạy chúng tôi thấy học sinh vẫn còn khó khăn trong việc phân tích bài toán để có thể áp dụng được thuật toán và cài đặt giải bài toán cụ thể. Với mỗi người có một cách dạy và phương pháp tiếp cận khác nhau xong mục đích cuối cùng đều muốn đưa đến cho học sinh lượng kiến thức cơ bản tốt nhất, để các em có thể áp dụng vào lớp bài toán khó với độ phức tạp tối ưu nhất. - TẦM QUAN TRỌNG CỦA TT SỐ HỌC Chính vì vậy chúng tôi đã tìm hiểu về chuyên đề “một số bài toán về số” giúp học sinh có được hệ thống kiến thức cơ bản về số học để giúp các em dễ dàng hơn trong giải quyết các bài toán cụ thể nhất là đối các bài toán về số học. II. ĐỐI TƯỢNG NGHIÊN CỨU Đối tượng là học sinh, sinh viên, giáo viên, đặc biệt là học sinh chuyên tin và tất cả những ai có quan tâm đến môn Tin học. III. MỤC ĐÍCH NGHIÊN CỨU, ĐÓNG GÓP MỚI CỦA CHUYÊN ĐỀ Khi viết chuyên đề này một lần nữa chúng được tìm hiểu lại các bài toán về số để giúp mình hiểu sâu và áp dụng vào các bài toán khác nhau. Để từ đó có phương pháp truyền đạt tốt nhất cho học sinh. Giúp học sinh thấy được vai trò của toán học đối với môn tin. Vận dụng kỹ thuật phân tích thiết kế để giải các bài toán thực tế: Các bài toán dạng nào thì có thể áp dụng được kỹ thuật này. Trên cơ sở các bài toán quên thuộc chúng tôi còn tìm hiểu thêm một số bài toán mở rộng để năng cao khả năng của bản thân cũng như đối với các đối tượng học sinh. 2
3. Chuyên đề: Một số bài toán về số IV. PHƯƠNG PHÁP NGHIÊN CỨU Để hoàn thành nhiệm vụ của chuyên đề, chúng tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh Chuyên tin, những vấn đề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài đặt chương trình. V. CẤU TRÚC CỦA CHUYÊN ĐỀ Ngoài phần mở đầu và kết luận chuyên đề còn được chia thành hai chương như sau: Phần 1: Mở đầu Phần 2: Nội dung chuyên đề Chương 1. Các thuật toán số học Chương 2: Một số bài toán về số Phần 3: Kết luận Phần 4. Tài liệu tham khảo 3
4. Chuyên đề: Một số bài toán về số Phần thứ hai NỘI DUNG CHUYÊN ĐỀ Chương 1. Các thuật toán số học I. Số nguyên tố 1. Định nghĩa: Một số tự nhiên n (n>1) là một số nguyên tố nếu nó có đúng 2 ước 1 và n. Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17,... 2. Kiểm tra tính nguyên tố Để kiểm tra tính nguyên tố của một số nguyên dương n, ta kiểm tra xem có tồn tại một số nguyên k (1<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 là số nguyên tố. Tuy nhiên, nếu n (n>1) không phải là số nguyên tố, ta luôn có thể tách n=k1 x k2 mà 2 1 k1 ≤n. Hay k1 ≤ √푛. Do đó việc kiểm tra từ 2 đến n-1 là không cần thiết, mà chỉ kiểm tra k từ 2 đến √푛. Code: #include using namespace std; bool isPrime(int n) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; } int main() { int num; cout << "Nhập số cần kiểm tra: "; cin >> num; if (isPrime(num)) cout << num << " YES.\n"; else cout << num << " NO\n"; return 0; } 4
5. Chuyên đề: Một số bài toán về số 3. Sàng nguyên tố (Eratosthenes) Sàng Eratosthenes là một thuật toán cổ xưa để tìm các số nguyên tố trong một đoạn các số tự nhiên. Mô tả thuật toán để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên n bằng sàng Eratosthenes, ta làm như sau: • Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 1 đến n: (1, 2, 3, 4,..., N). • Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố (ngoại trừ số 1 không là số nguyên tố). Trong đó, p=2 là số nguyên tố đầu tiên. • Bước 3: Tất cả các bội của số nguyên tố p như 2p, 3p, 4p sẽ bị đánh dấu vì không phải là số nguyên tố. • Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p và nhỏ hơn hoặc bằng √푛 .Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3. Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm. Ta có thể cải tiến thuật toán: Xét X=k x p là bội của số nguyên tố p. Nếu p<X<p2, ta có 1<k<p. Suy ra k phải có ước nguyên tố nhỏ hơn P. Vì thế các bội X=k x p (X<p2) đã bị sàng Eratosthenes loại bỏ trong các vòng lặp trước đó và ta chỉ cần xét X>p2. #include #include using namespace std; void sang(int n) { if (n < 2) { cout << n << ".\n"; return; } vector isPrime(n + 1, true); // Khởi tạo mảng đánh dấu isPrime[0] = isPrime[1] = false; // 0 và 1 không phải số nguyên tố for (int p = 2; p * p <= n; p++) { if (isPrime[p]) { // Nếu p là số nguyên tố for (int i = p * p; i <= n; i += p) { // Đánh dấu các bội của p isPrime[i] = false; } } } // In ra các số nguyên tố 5
6. Chuyên đề: Một số bài toán về số cout << "Các số nguyên tố nhỏ hơn hoặc bằng " << n << " là:\n"; for (int i = 2; i <= n; i++) { if (isPrime[i]) { cout << i << " "; } } cout << endl; } int main() { int n; cout << "Nhập số nguyên dương n: "; cin >> n; sang(n); return 0; } Với sàng nguyên tố ta áp dụng rất nhiều trong bài toán liệt kê số nguyên tố trong đoạn, giảm được độ phức tạp trong các bài toán lớn. 4. Phân tích một số ra thừa số nguyên tố Phân tích một số tự nhiên n (n>1) ra thừa số nguyên tố là viết số đó dưới dạng một tích các thừa số nguyên tố. Ví dụ: 300 = 6.50 = 2.3.2.25 = 2.3.2.5.5 Chú ý: • Dạng phân tích thành thừa số nguyên tố của mỗi số nguyên tố chính là số đó. Ví dụ: 37 = 1.37, 149 = 1.149, 853 = 1.853 • Mọi hợp số đều phân tích được thành tích của các thừa số nguyên tố. Ví dụ: 68 = 2^2.17, 306 = 2.3^2. 17, 982 = 2.491 Thuật toán: 1. Duyệt các số d từ 2 tới √ 2. Nếu N chia hết cho d thì tiến hành lấy N chia cho d cho tới khi còn chia hết 3. Sau khi duyệt xong các số từ 2 tới √N mà N vẫn khác 1 thì N chính là thừa số nguyên tố cuối cùng #include #include using namespace std; void factorize(int n) { if (n <= 1) return; cout << n << " = "; 6
7. Chuyên đề: Một số bài toán về số // Xử lý thừa số 2 riêng biệt int count = 0; while (n % 2 == 0) { count++; n /= 2; } if (count > 0) { cout << "2"; if (count > 1) cout << "^" << count; if (n > 1) cout << " * "; } // Duyệt các số lẻ từ 3 đến sqrt(n) for (int i = 3; i <= sqrt(n); i += 2) { count = 0; while (n % i == 0) { count++; n /= i; } if (count > 0) { cout << i; if (count > 1) cout << "^" << count; if (n > 1) cout << " * "; } } // Nếu còn lại số nguyên tố cuối cùng if (n > 1) cout << n; cout << endl; } int main() { int num; cout << "Nhập số cần phân tích: "; cin >> num; factorize(num); return 0; } II.Ước số bội số 1. 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 x bj x...x ck Khi đó ước số của N có dạng: ap x bq x....x cr trong đó: 7
8. Chuyên đề: Một số bài toán về số 0≤ p≤ i, 0 ≤q≤ j,..., 0 ≤r ≤k. Do đó số ước của N là: (i+1) x (j+1) x....x (k+1) Ví dụ1: Cho số N=12 ta phân tích thành thừa số nguyên tố: 12=22 x 31 Số ước của N được tính theo công thức:(2+1)×(1+1)=6 Các ước của 12: 1, 2, 3, 4, 6, 12 Ví dụ 2: Cho số N=100 ta phân tích thành thừa số nguyên tố: 100=22×52 Số ước của N là: (2+1)×(2+1)=9 Các ước của 100: 1, 2, 4, 5, 10, 20, 25, 50, 100 2. Tổng các ước số của một số N=ai x bj x...x ck Đặt N1= bj x...x ck Gọi F(N) là tổng các ước của N, ta có ( 푖+1−1) F(N) = F(N1)+a x F(N1)+...+a x F(N1) =(1+a+...+ai) x F(N1)= x F(N1) −1 ( 푖+1−1) ( 푗+1−1) ( +1−1) = x x....x −1 −1 −1 (22+1−1) (52+1−1) Ví dụ: Tổng các ước của 100 là: x =217 2−1 5−1 3. Bài toán đếm ước, tổng ước của N Cho số nguyên dương N (N≤109), hãy đếm số ước của N và tính tổng các ước của N. #include using namespace std; typedef long long ll; pair count_and_sum_divisors(ll N) { ll original_N = N; ll count_divisors = 1; ll sum_divisors = 1; // Xử lý các số nguyên tố nhỏ nhất là 2 if (N % 2 == 0) { ll exp = 0; ll sum_p = 1; ll term = 1; while (N % 2 == 0) { N /= 2; exp++; term *= 2; sum_p += term; } 8
9. Chuyên đề: Một số bài toán về số count_divisors *= (exp + 1); sum_divisors *= sum_p; } // Duyệt các số lẻ từ 3 đến sqrt(N) for (ll factor = 3; factor * factor <= N; factor += 2) { if (N % factor == 0) { ll exp = 0; ll sum_p = 1; ll term = 1; while (N % factor == 0) { N /= factor; exp++; term *= factor; sum_p += term; } count_divisors *= (exp + 1); sum_divisors *= sum_p; } } // Nếu N còn lại là số nguyên tố lớn hơn 1 if (N > 1) { count_divisors *= 2; sum_divisors *= (1 + N); } return {count_divisors, sum_divisors}; } int main() { ll N; cout << "Nhập N: "; cin >> N; pair result = count_and_sum_divisors(N); cout << "Số lượng ước của " << N << ": " << result.first << endl; cout << "Tổng các ước của " << N << ": " << result.second << endl; return 0; } 4. Ước số chung lớn nhất của hai số Ước số chung lớn nhất của 2 số (UCLN) của hai số được tính theo thuật toán Euclid UCLN(a,b)=UCLN(b,(amod b)) 5. Bội số chung nhỏ nhất của 2 số Bội chung nhỏ nhất (BCNN) của hai số được tính theo công thức: 9
10. Chuyên đề: Một số bài toán về số BCNN(a,b)= 푈 퐿 ( , ) III. Số Fibonacci 1. Định nghĩa Số Fibonacci được xác định bởi công thức sau: * Số Fibonacci là đáp án của bài toán: - Các con thỏ không bao giờ chết; - Hai tháng sau khi ra đời, mỗi cặp thỏ mới sinh 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 ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp. *Sự kì diệu trong tự nhiên Trong tự nhiên có nhiều điều trùng hợp với dãy số Fibonacci hay tỉ lệ vàng. Hầu hết các bông hoa có số cánh hoa là một trong các số: 3, 5, 8, 13, 21, 34, 55 hoặc 89. Ví dụ: Hoa loa kèn có 3 cánh, hoa mao lương vàng có 5 cánh, hoa cải ô rô thường có 8 cánh, hoa cúc vạn thọ có 13 cánh, hoa cúc tây có 21 cánh, hoa cúc thường có 34, hoặc 55 hoặc 89 cánh. 10
11. Chuyên đề: Một số bài toán về số 2. Bài toán số Fibonaci và số nguyên tố Tính số Fibonaci thứ N, và cho số M (0<M<29) hãy đưa ra sô Fibonaci lớn nhất là số nguyên tố và nhỏ hơn M. Ý tưởng thuật toán với code tối ưu Chương trình gồm ba phần chính: Hàm kiểm tra số nguyên tố (isPrime) Hàm tính số Fibonacci thứ Hàm tìm số Fibonacci nguyên tố lớn nhất nhỏ hơn + Hàm kiểm tra số nguyên tố isPrime(long long num) • Nếu num<2thì không phải số nguyên tố. • Nếu num=2 trả về true vì chúng là số nguyên tố. • Nếu num chia hết cho 2 hoặc 3, trả về false (loại bỏ số chẵn và bội số của 3). • Kiểm tra số nguyên tố bằng cách chia thử với các số từ 5 đến sqrt(num), bước nhảy 6 (vì số nguyên tố lớn hơn 3 luôn có dạng 6k±1). + Hàm tính số Fibonacci thứ NNN (fibonacci(int n)) • Nếu N=0, trả về 0, nếu N=1, trả về 1. • Dùng biến a và b để lưu hai số Fibonacci gần nhất. • Cập nhật c = a + b cho đến khi tính được số Fibonacci thứ N. + Hàm tìm số Fibonacci nguyên tố lớn nhất nhỏ hơn M • Sinh dãy Fibonacci nhỏ hơn M bằng cách cập nhật ba biến a, b, c như trên. • Kiểm tra từng số Fibonacci ngay khi nó được tạo ra xem có phải số nguyên tố không. 11
12. Chuyên đề: Một số bài toán về số • Nếu là số nguyên tố, lưu lại vào lastPrime. • Tiếp tục sinh số Fibonacci cho đến khi c≥M • Trả về lastPrime là số Fibonacci nguyên tố lớn nhất nhỏ hơn M. #include using namespace std; // Hàm kiểm tra số nguyên tố bằng cách chia thử tối ưu bool isPrime(long long num) { if (num < 2) return false; if (num == 2 || num == 3) return true; if (num % 2 == 0 || num % 3 == 0) return false; for (long long i = 5; i * i <= num; i += 6) { if (num % i == 0 || num % (i + 2) == 0) return false; } return true; } // Hàm tính số Fibonacci thứ N long long fibonacci(int n) { if (n <= 1) return n; long long a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } // Tìm số Fibonacci lớn nhất là số nguyên tố và nhỏ hơn M long long largestFibonacciPrime(long long M) { long long a = 0, b = 1, c = 1, lastPrime = -1; while (c < M) { if (isPrime(c)) lastPrime = c; a = b; b = c; c = a + b; } return lastPrime; } int main() { int N; long long M; cout << "Nhập N: "; cin >> N; cout << "Nhập M (0 < M < 2000000000): "; cin >> M; 12
13. Chuyên đề: Một số bài toán về số if (M = 2000000000) { cout << "M không hợp lệ!\n"; return 1; } cout << "Số Fibonacci thứ " << N << " là: " << fibonacci(N) << endl; long long result = largestFibonacciPrime(M); if (result != -1) cout << "Số Fibonacci nguyên tố lớn nhất nhỏ hơn " << M << " là: " << result << endl; else cout << "Không có số Fibonacci nguyên tố nào nhỏ hơn " << M << "\n"; return 0; } IV. Số Catalan Là dãy các số tự nhiên xuất hiện trong nhiều bài toán đếm, thường bao gồm những đối tượng đệ quy. Số Catalan được xác định bởi công thức: 1 푛 (2푛)! Catalann= = với n≥0 푛+1 2푛 (푛+1)!푛! Một số phần tử đầu tiên của dãy Catalan là: N 0 1 2 3 4 5 6 ... . Catalan 1 1 2 5 1 4 13 ... n 4 2 2 Số Catalan là đáp án của các bài toán: 1. Bài toán đặt ngoặc: Cho trước số nguyên không âm N. Hãy đếm số cách khác nhau để đặt N ngoặc mở và N ngoặc đóng đúng đắn. Ví dụ: n=3 ta có 5 cách sau: ((( ))), (( )( )), (( ))( ), ( )(( )), ( )( )( ), 2. Đếm cây nhị phân: Cho trước số nguyên không âm N. Hãy đếm số cây nhị phân có đúng (n+1) lá? 3. Chia đa giác: Cho một đa giác lồi gồm (N+2) đỉnh. Ta chia đa giác thành các tam giác bằng cách 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? Ví dụ: n=4 13
14. Chuyên đề: Một số bài toán về số 4. Cài đặt: Chương trình tính số catalan thứ N (N≤106) và đưa ra kết quả là mod 109+7. #include #include using namespace std; const int MOD = 1e9 + 7; const int MAX_N = 1e6; vector fact(2 * MAX_N + 1), inv_fact(2 * MAX_N + 1); // Hàm tính lũy thừa theo modulo long long powMod(long long base, long long exp, int mod) { long long result = 1; while (exp > 0) { if (exp % 2 == 1) result = result * base % mod; base = base * base % mod; exp /= 2; } return result; } // Hàm tiền xử lý giai thừa và nghịch đảo giai thừa void precompute_factorials(int n, int mod) { fact[0] = 1; for (int i = 1; i <= 2 * n; ++i) { fact[i] = fact[i - 1] * i % mod; } inv_fact[2 * n] = powMod(fact[2 * n], mod - 2, mod); for (int i = 2 * n - 1; i >= 0; --i) { inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod; } } 14
15. Chuyên đề: Một số bài toán về số // Hàm tính số Catalan thứ N long long catalan_number(int n, int mod = MOD) { return fact[2 * n] * inv_fact[n + 1] % mod * inv_fact[n] % mod; } int main() { int N; cin >> N; precompute_factorials(N, MOD); cout << catalan_number(N) << endl; return 0; } Mỗi một bài toán từ dễ đến khó, từ học sinh chuyên đến học sinh không chuyên đều sẽ được tiếp cận với những bài toán số học trên. Với những cách phát biểu, tiếp cận và giải quyết khác nhau xong những bài toán trên không thể thiếu trong Tin học. 15
16. Chuyên đề: Một số bài toán về số Chương 2: Một số bài toán về số I. Bài tập có hướng dẫn Bài 1. Bài toán số nguyên tố tương đương Hai số tự nhiên được gọi là nguyên tố tương đương nếu chúng có cùng các ước nguyên tố. Ví dụ: các số 75 và 15 là số nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên M và N. Hãy viết chương trình kiểm tra xem các số này có tương đương hay không. Ví dụ: input output 15 75 YES Ý tưởng chính của chương trình • Tìm tập hợp các ước số nguyên tố của từng số M và N. • So sánh hai tập hợp: nếu chúng giống nhau thì hai số tương đương, ngược lại thì không Thuật toán Tạo hàm prime_factors(int num) o Duyệt từ 2 đến num √푛 để tìm các ước số nguyên tố của num. o Nếu một số i là ước của num, thêm i vào tập hợp factors và chia num cho i nhiều lần đến khi không chia hết. o Nếu num sau vòng lặp vẫn lớn hơn 1, nghĩa là num là số nguyên tố, thêm num vào factors. So sánh hai tập hợp ước số nguyên tố của MMM và NNN o Nếu hai tập hợp bằng nhau, in "YES" (tương đương). o Ngược lại, in "NO" (không tương đương). Độ phức tạp của chương trình O√ đủ nhanh cho N lớn. #include #include using namespace std; // Hàm tìm tập hợp các ước số nguyên tố của một số set prime_factors(int num) { set factors; for (int i = 2; i * i <= num; i++) { while (num % i == 0) { factors.insert(i); 16
17. Chuyên đề: Một số bài toán về số num /= i; } } if (num > 1) { factors.insert(num); } return factors; } int main() { int M, N; cin >> M >> N; if (prime_factors(M) == prime_factors(N)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; } Bài 2. Bài toán FIBOK, tên bài FIBOK 6 Xét dãy F gồm n (2 ≤ n ≤ 15x10 ) số nguyên, F = (f1, f2, , fn) định nghĩa như sau: 1 푛ế 1 ≤ 푖 ≤ 2 푖 = { 7 ( 푖−1 + 푖−2) 표 10 푛ế 2 < 푖 ≤ 푛. Yêu cầu: hãy cho biết nếu sắp xếp dãy F theo thứ tự không giảm thì số thứ k (k ≤ n) có giá trị là bao nhiêu và có bao nhiêu giá trị như vậy? Input: chứa số n và k. Output: lần lượt ghi 2 số nguyên theo yêu cầu. Ví dụ: FIBOK.inp FIBOK.out 4 3 2 1 Hướng dẫn: - Tính dãy f theo công thức đã cho - SX dãy f thứ tự không giảm - Output(f[k]) Với n lớn thì cách làm trên chưa đủ hiệu quả. Cách khác: nhận thấy với n lớn, và giá trị mảng f từ 0 đến 107 nên dùng cách đến phân phối. Gọi c[i] là số lượng giá trị I của dãy f, c[i]=0 nếu không tồn tại I trong dãy f Code 17
18. Chuyên đề: Một số bài toán về số Code 1 #include #include const int oo=10000000; const int mn=15000008; using namespace std; int f[mn],c[mn],n=12000000,k=11000000; string fol="",fi=fol+"FIBOK.inp",fo=fol+"FIBOK.out"; void out(){ int i=k-1,j=k+1; while (i>=0 && f[i]==f[k]) i--; while (j<=n && f[j]==f[k]) j++; cout<<f[k]<<' '<<j-i-1; } int main(){ freopen(fi.c_str(),"r",stdin); freopen(fo.c_str(),"w",stdout); cin>>n>>k; f[1]=f[2]=1; f[0]=0; for(int i=3;i<=n;i++){ f[i]=(f[i-1]+f[i-2]) % oo; } sort(f+1,f+n+1); out(); } Code2: #include using namespace std; const long long mod=1e7; const int maxn=2e7+7; int n,k,d[maxn],f[maxn]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen("FIBOK.inp","r",stdin); freopen("FIBOK.out","w",stdout); cin>>n>>k; f[1]=1;f[2]=1;d[1]=2; for(int i=3;i<=n;i++){ f[i]=f[i-1]+f[i-2]; f[i]%=mod; d[f[i]]++; } int ii=1; for(int i=0;i<mod;i++){ 18
19. Chuyên đề: Một số bài toán về số k-=d[i]; if(k<=0) { ii=i; break; } } cout<<ii<<" "<<d[ii]; return 0; } Bài 3. Bài toán Mưu sĩ và nhà vua, tên bài GOLD Tương truyền rằng, ngày xưa có một mưu sĩ thấy dân chúng quá nghèo khổ nên ông ta đã đến thách đố đánh cờ cùng nhà vua nhằm lấy thóc trong kho đem phân phát cho dân nghèo. Nhà vua ra điều kiện nếu đánh thua nhà vua thì mưu sĩ sẽ bị chém đầu, ngược lại mưu sĩ sẽ được trọng thưởng bằng vật chất. Nếu đánh thắng cờ với nhà vua, mưu sĩ chỉ xin một điều đó là trong mỗi ô cờ gồm 8x8 ô thì lần lượt bỏ vào ô thứ 1: 1 hạt thóc, ô thứ 2: 1x2 hạt thóc, ô thứ 3: 1x2x3 hạt thóc, cho đến ô cuối cùng. Nhà vua nghe qua rất khoái chí và đồng ý ngay. Sau lần đấu cờ đó nhà vua đã mất rất nhiều kho lương thực cho dân nghèo. Do bản tính hiếu thắng của nhà vua, ông vẫn tiếp tục thách đấu với những tay cao thủ cờ khác trong thiên hạ nhưng bây giờ rút kinh nghiệm ông chỉ xuất trong kho ra bây giờ không phải là thóc nữa mà là vàng. Nguyên tắc để nhận được vàng sau khi đánh thắng nhà vua như sau: 1. Mỗi ô trong bàn cờ có một số. Con số này được gán vào như sau: - Ô số 1: 1 - Ô số 2: 1x2 = 2 - Ô số 3: 1x2x3 = 6 - Ô số 10 1x2x3x .x10 = 3 628 800 - Ô số 21 1x2x3x .x21 = 51 090 942 171 709 440 000 2. Số vàng nhận được chính là con số khác không đầu tiên kể từ hàng đơn vị lên phía trước của ô mà đối thủ sẽ chọn. Ví dụ, chọn ô số 10 thì sẽ được 8 lạng vàng, ô số 21 sẽ được 4 lạng vàng, 3. Đối thủ chỉ được chọn mỗi lần một ô để nhận vàng. 4. Bàn cờ dùng thi đấu là bàn cờ 8x8, nhưng bàn cờ để chọn vàng là NxN, các ô được đánh số liên tục từ 1đến N. Yêu cầu: Tìm số vàng mà đấu thủ nọ nhận được khi chọn một ô. 19
20. Chuyên đề: Một số bài toán về số Dữ liệu: Vào từ file văn bản GOLD.INP gồm 1 số nguyên N là số thứ tự của ô mà đấu thủ chọn (1 ≤ N ≤1015) Kết quả: Ghi ra file văn bản GOLD.OUT 1 số duy nhất là số vàng đấu thủ nhận được Ví dụ: GOLD.INP GOLD.OUT 10 8 Hướng dẫn: Bài toán này có nhiều cách phân tích và giải quyết vấn đề, dưới đây, tui xin đưa ra cách khá hiệu quả và giải quyết bài toán một cách đơn giản. Bài toán này được phát biểu toán học như sau: Tìm số cữ số 0 tận cùng của N! ta nhận thấy những số 0 trong kết quả là do cặp (2,5) tạo ra, như vậy kết quả của bài toán là đi tìm số cặp (2,5). Ta lại có nhận xét, trong kết, số chữ số 2 (lũy thừa 2) luôn nhiều hơn lũy thừa 5, suy ra, vấn đề được giải quyết là tìm ra số lũy thừa 5 trong N! Từ đây ta nghĩ đến phương án đến tất cả các lũy thừa 5 bằng cách phân tích các số i (1..N) ra thừa số nguyên tố và tính tổng lũy thừa 5 (hoặc chỉ phân tích lũy thừa 5) Tuy nhiên cách trên cũng chưa hiệu quả. Có một cách tốt hơn như code dưới đây Code: Code 1: #include #define ll long long using namespace std; ll n,res; ll count5(ll i){ ll m,r; m=0;r=i%5; while ((i!=0)and(r==0)){ m=m+1; i=i/5; r=i%5; } return m; } int main(){ freopen("zero.inp","r",stdin); freopen("zero.out","w",stdout); cin>>n; int d=0,i=5; 20