Editorial for Bedan Contest #05 - E - Tổng chữ số


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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.


Comments

There are no comments at the moment.