Cho số nguyên dương n nhiệm vụ của bạn là hãy xác định xem có bao nhiêu ước số của n chia hết cho 2

Bai tap co ban lap trinh C

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [985.86 KB, 41 trang ]

NOTE: Mọi thắc mắc về đầu bài, các bạn gửi email cho mình theo địa chỉ sau
.
Mỗi bài tốn thường có 3 ví dụ, ở đây mỗi bài mình chỉ lấy 1 ví dụ, để xem
thêm nhiều ví dụ của bài tốn cũng như phần giải thích ví dụ[nếu có] các bạn
truy cập theo địa chỉ nộp bài ở cuối mỗi bài.
Implementation Problems.

476A.
Dreamoon muốn leo lên một cầu thang gồm n bước. Anh ta có thể leo 1 hoặc 2
bước mỗi lần di chuyển. Dreamoon muốn số lần di chuyển là bội số của một số
nguyên m.
Số lượng di chuyển tối thiểu làm cho anh ta leo lên đỉnh cầu thang thỏa mãn điều
kiện của anh ta là gì?
Input
Dịng đơn chứa hai số nguyên cách nhau n, m [0

Chắc hẳn, ai trong chúng ta cũng đã quá quen thuộc với bài toán đếm số ước nguyên dương của $n$. Giải thuật thông thường nhất mà mọi người thường sử dụng là giải thuật O[n],O[\sqrt{n}],O[n​], dựa trên một nhận định rằng nếu như số $n$ có một ước là i [1≤i≤n]i \ [1 \le i \le \sqrt{n}]i [1≤i≤n​] thì nó cũng sẽ có một ước nữa là ni [n≤ni≤n]\frac{n}{i} \ \left[\sqrt{n} \le \frac{n}{i} \le n \right]in​ [n​≤in​≤n]. Bằng phương pháp này, chúng ta có thể giải quyết mọi bài toán với giới hạn $n$ khoảng 101510^{15}1015 trở xuống [Các bạn xem lại trong chuyên đề Tìm các ước của một số nguyên].

Một phương pháp hay khác mà chúng ta cũng sử dụng là phân tích thừa số nguyên tố và đếm ước của $n$ dựa trên phân tích nguyên tố của nó. Cách làm này có thể khiến thao tác đếm ước của số $n$ giảm xuống độ phức tạp $O[\log [n]]$ khi kết hợp với sàng lọc số nguyên tố, và thường được áp dụng trong các bài toán multi-testcase [các bạn xem lại trong chuyên đề Số nguyên tố]. Tuy nhiên, nhược điểm của phương pháp này là bạn buộc phải tạo ra được một mảng có độ dài $n$ để đánh dấu các số nguyên tố, đồng nghĩa với việc nếu n≤109,n \le 10^9,n≤109, các bạn không thể sử dụng được nó.

Điều gì sẽ xảy ra khi chúng ta cần đếm ước của một số nguyên dương n≤1018?n \le 10^{18}?n≤1018? Phân tích thừa số nguyên tố? Không thể, vì ta không thể sàng lọc được số nguyên tố ở giới hạn này. Vậy phân tích theo phương pháp O[n]O[\sqrt{n}]O[n​] truyền thống thì sao? Cũng không thể, vì O[n]≈O[109],O[\sqrt{n}] \approx O[10^9],O[n​]≈O[109], độ phức tạp này không đủ tốt. Khi đó, người ta sử dụng phương pháp đếm ước trong O[n13],O[n^{\frac{1}{3}}],O[n31​], một phương pháp rất hiệu quả nhưng lại được ít người biết đến, có lẽ vì chúng ta không thường xuyên gặp phải những bài toán như vậy. Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu ý tưởng và cách cài đặt của phương pháp này bằng C++. Trước khi đọc bài viết, các bạn cần có kiến thức đầy đủ về sàng lọc số nguyên tố, đếm ước theo phương pháp thông thường cũng như kĩ năng code ở mức khá. Nếu chưa nắm được những kiến thức này, các bạn hãy quay lại nghiên cứu những chuyên đề cũ mà mình đã để link ở trên nhé!

II. Phương pháp đếm số ước của một số trong O[n13]O[n^{\frac{1}{3}}]O[n31​]

Để sử dụng được giải thuật đếm ước trong O[n13],O[n^{\frac{1}{3}}],O[n31​], trước tiên ta cần tìm hiểu về phương pháp của Fermat dùng để kiểm tra tính nguyên tố của một số. Đây là một phương pháp kiểm tra nguyên tố có tính xác suất, nghĩa là nó có thể xảy ra trường hợp sai, tuy nhiên, trong giải thuật này sự sai khác đó có thể chấp nhận được.

Ý tưởng: Phương pháp kiểm tra tính nguyên tố của Fermat được xây dựng dựa trên định lý Fermat nhỏ: Nếu $n$ là một số nguyên tố, thì với mọi giá trị $a$ sao cho 1≤a