Bóng đèn và những vị khách bí ẩn
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Trong một tòa lâu đài cổ có Rất nhiều bóng đèn được đánh số từ 1. Ban đầu, tất cả các bóng đèn đều tắt.
Bỗng một nhóm ~N~ vị khách bí ẩn bước vào lâu đài. Mỗi người có một quy tắc kỳ lạ khi tương tác với bóng đèn:
- Người thứ ~i~ sẽ đổi trạng thái (bật nếu đang tắt, tắt nếu đang bật) của tất cả các bóng đèn có vị trí là bội số của ~i~.
- Ví dụ: Người thứ 2 sẽ đổi trạng thái các bóng đèn 2, 4, 6, 8, ...
- Người thứ 3 sẽ đổi trạng thái các bóng đèn 3, 6, 9, 12, ...
Sau khi tất cả ~N~ người đã bước vào và hoàn thành công việc của mình, ta quan sát dãy bóng đèn từ vị trí ~A~ đến ~B~ và thấy rằng có những bóng đèn vẫn đang sáng.
Input
- ~N~ (~1 ≤ N ≤ 10^{12}~) - Là số người vào lâu đài.
- ~A, B~ (~1 ≤ A ≤ B ≤ N~) - Khoảng bóng đèn cần kiểm tra.
Output
- Một số nguyên duy nhất - số lượng bóng đèn đang sáng trong đoạn ~[A, B]~ sau khi tất cả ~N~ người đã thực hiện quy tắc của mình.
🔥 Ràng buộc (Subtask)
| Subtask | Giới hạn của N |
|---|---|
| 1 | ~(N \leq 10^{3})~ |
| 2 | ~(N \leq 10^{6})~ |
| 3 | ~(N \leq 10^{9})~ |
| 4 | ~(N \leq 10^{12})~ |
Sample Input 1
5
1 5
Sample Output 1
2
Sample Input 2
3
1 3
Sample Output 2
1
Sample Input 3
100
1 100
Sample Output 3
10
Bình luận
i hate that misconception input.
that is your fault :)))