Nuôi Đủ Số Lượng · canuc80k1402

Ban đầu một chiếc hộp không có vi khuẩn. Mỗi ngày diễn ra theo quy tắc sau:

Bạn muốn tại một thời điểm nào đó hộp có đúng $x$ vi khuẩn. Hãy tìm tổng số vi khuẩn ít nhất phải trực tiếp thêm vào hộp trong suốt quá trình.

$1 \leq x \leq 1 0^{9}$ .
Có thể dừng ngay sau một buổi sáng hoặc một buổi tối, miễn số lượng trong hộp bằng $x$ .

Subtask $1$ ( $50$ điểm): $10$ test nhỏ, có thể dựng quá trình tăng số lượng trực tiếp.
Subtask $2$ ( $50$ điểm): $10$ test đầy đủ; test $19$ và $20$ là hai số lớn có cấu trúc bit khác nhau.

Test 1

Input

Output

Giải thích: Ta có thể thêm một vi khuẩn để tạo các nhóm lần lượt phát triển thành $8, 4$ và $1$ con; tổng số đã thêm là $3$ .

Ý tưởng: Một vi khuẩn được thêm vào rồi trải qua $k$ lần phân chia sẽ tạo ra đúng $2^{k}$ vi khuẩn ở thời điểm dừng. Vì thế ta cần biểu diễn $x$ thành tổng của ít nhất số lượng lũy thừa của hai; số hạng tối thiểu chính là số bit 1 trong biểu diễn nhị phân của $x$ .
Chứng minh đúng đắn: Mỗi vi khuẩn được thêm trực tiếp có một thời điểm thêm xác định. Nếu sau đó còn $k$ buổi tối trước khi dừng, đóng góp cuối cùng của nó là $2^{k}$ . Do đó mọi quá trình dùng $q$ vi khuẩn trực tiếp tạo ra một biểu diễn của $x$ thành tổng của $q$ lũy thừa của hai.
Chứng minh đúng đắn: Khi gộp các lũy thừa bằng nhau theo quy tắc $2^{k} + 2^{k} = 2^{k + 1}$ , một biểu diễn như vậy không thể có ít số hạng hơn số bit 1 của $x$ . Ngược lại, với mỗi bit 1 ở vị trí $k$ , ta thêm một vi khuẩn đúng $k$ buổi tối trước khi dừng; các đóng góp cộng lại thành $x$ . Vì vậy số nhỏ nhất phải thêm là $popcount (x)$ .
Độ phức tạp: Thời gian là $O (1)$ trên kiểu số nguyên máy và bộ nhớ phụ là $O (1)$ .