Hướng dẫn cho Bedan Contest #05 - E - Tổng chữ số

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Cách giải

Hint

Số lượng số nguyên dương $n$ thỏa mãn tồn tại một số nguyên dương $x$ thỏa mãn $x+S(x) = n$ rất là nhiều, và thường thì chỉ có $9$ số liên tiếp không có mà thôi. Từ nhận xét cực kì lỏ trên, ta có thể đặt $y$ là các số trong khoảng $[1, 9]$ .
Một sự thật thú vị là nhận xét trên được mình phát hiện nhờ việc in bừa.

Solution

Với mỗi $y$ thỏa mãn $1 \le y \le 9$ , ta chỉ việc kiểm tra $n-2\times y$ có thỏa mãn tồn tại một số nguyên dương $x$ thỏa mãn $x+S(x) = n-2\times y$ hay không. Để tìm được số nguyên dương $x$ vậy, ta có nhận xét rằng $0 \le S(x) \le 162$ bởi $1 \le x \le 10^{18}$ . Vì vậy với mỗi giá trị $S(x)$ từ $1$ đến $162$ , ta chỉ cần kiểm tra $S(n-S(x)) = S(x)$ hay không.
Ngoài ra sẽ có một vài số rất đặc biệt và lỏ không có cặp $(x, y)$ là các số $2, 3, 5, 7, 9, 11$ .
Độ phức tạp của cách trên trong trường hợp tệ nhất là $O(t \times 162 \times log_{10}n)$ , tuy nhiên phần lớn kết quả sẽ tìm ra nhanh chóng nên độ phức tạp thực tế sẽ nhỏ hơn nhiều.
Ngoài cách giải trên ra, mình thấy ngài icebearlovecode sử dụng chặt nhị phân kết quả để giải.

Bình luận

Không có bình luận nào.