#1417. DECOR - Hệ thống đèn màu

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Lê Minh Hoàng ôn Hải Phòng T10/2016

Để trang trí cho một lễ hội, ban tổ chức đã dùng một hệ thống đèn mầu gồm 𝑛 đèn đánh số từ 1 đến 𝑛 . Mỗi đèn có khả năng sáng màu xanh hoặc màu đỏ. Các đèn được điều khiển theo quy tắc sau:

  • Bấm công tắc lần 1 , tất cả các đèn đều sáng màu xanh;
  • Bấm công tắc lần 2 , tất cả các đèn có số thứ tự chia hết cho 2 sẽ đổi màu (xanh thành đỏ và ngược lại);
  • Bấm công tắc lần 3 , tất cả các đèn có số thứ tự chia hết cho 3 sẽ đổi màu (xanh thành đỏ và ngược lại);

Yêu cầu: Xác định số đèn sáng màu xanh sau 𝑛 lần bấm công tắc.

Ví dụ: 𝑛 = 6 :

  • Bấm công tắc lần 1 : XXXXXX
  • Bấm công tắc lần 2 : XDXDXD
  • Bấm công tắc lần 3 : XDDDXX
  • Bấm công tắc lần 4 : XDDXXX
  • Bấm công tắc lần 5 : XDDXDX
  • Bấm công tắc lần 6 : XDDXDD

Dữ liệu vào:

  • Một dòng duy nhất chứa số nguyên dương 𝑛 ≤ 10^{18} ;

Dữ liệu ra:

  • Ghi ra số đèn xanh sau lần bấm công tắc thứ 𝑛 .

Ví dụ:

Dữ liệu vào:
6
Dữ liệu vào:
2