Tìm số nguyên dương nhỏ nhất chia hết cho N, và tổng các chữ số của nó cũng chia hết cho N
Bài toán của mình là cho số nguyên N dương, tìm số nguyên dương nhỏ nhất thỏa mãn chia hết cho N và tổng các chữ số của nó cũng chia hết cho N. Mới đầu, mình mới nghĩ đến giải thuật kiểu naive, kiểm tra lần lượt từng bội số của N, những bội nào có tổng các chữ số chia hết cho N thì mình xuất ra. Nhưng với đầu vào là 100 trở lên thì chạy rất lâu. Mình có để ý quy luật( tuy chưa chứng minh được) : số cần tìm có tổng các chữ số chính bằng số N. bài toán của mình muốn hỏi là sắp xếp N con 1 đứng cạnh nhau, đặt các khe vào giữa các con 1 đó( không giới hạn số khe), sao cho số tạo thành chia hết cho N, Ví dụ như cho N=12, số cần tìm là 48 ( 1111|11111111) ; cho N=58 số cần tìm là 8988898(8/9/8/8/8/9/8).
Mình nghĩ lời giải bài toán này có lẽ không đến từ một giải thuật “trâu chó” như cách nghĩ của mình ban đầu, có lẽ nó sẽ được giải quyết thông qua bài Toán rời rạc kia. Mong mọi người giúp đỡ.
Dưới đây là chương trình của mình ban đầu, có điều là đầu vào lớn hơn 60 thì khó mà đợi nổi nó chạy
http://codepad.org/Qze0QTab
Cậu có thể nói rõ hơn cho tớ về việc tính số chữ số tối thiểu không, vì tớ đang học bên Điện tử- Viễn thông, mới năm hai thôi, tớ chưa học môn Toán rời rạc. Tớ biết bài tìm số này thuộc loại toán rời rạc vì tớ có một lần nghe giảng lớp toán rời rạc của bên Viện CNTT
Dễ thấy nếu tổng>9*k thì đáp án phải có nhiều hơn k chữ số.
Có lẽ giải thuật c đưa ra cũng không khả thi, nếu t không hiểu nhầm ý cậu.
Dễ thấy số tập con sinh ra từ n phần tử là 2^n, việc mình chia không giới hạn số khe vào n-1 khe, chỉ cần không quá n-1. Việc này sẽ sinh ra 2^(n-1) tập con, ứng với bấy nhiêu đó trường hợp.
=> độ phức tạp thuật toán 2^n !!!
Thì mình chỉ dựa vào rồi viết lại thuật toán bạn đưa ra mà thôi. Có hai cách để lượng giá là precompute các lũy thừa của 10 modulo N (sạch sẽ hơn) và Horner.
Nếu bạn dùng quay lui nhánh cận thì không đến nỗi đâu, khoảng 3^(N/9) là cao.