Chọn ĐTQG Hà Nội 2025 - Nguyên tố
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Hai số nguyên dương ~a, b~ được gọi là nguyên tố cùng nhau khi ước chung lớn nhất của chúng là 1. Cho hai số nguyên dương ~N~ và ~Q~.
Yêu cầu: Thực hiện ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L, R~. Hãy đếm số lượng số nguyên tố cùng nhau với ~N~ trong đoạn ~[L, R]~.
Input
Dòng đầu tiên gồm hai số nguyên dương ~N, Q~ ~(1 \le N \le 10^{11}; 1 \le Q \le 3 \times 10^4)~;
~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L, R~ ~(1 \le L \le R \le 10^{15})~ mô tả truy vấn.
Output
Gồm ~Q~ dòng, mỗi dòng in ra kết quả của truy vấn tương ứng.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~R \times Q \le 10^6~ |
| 2 | ~20\%~ | ~R \le 10^6~ |
| 3 | ~20\%~ | ~N~ là lũy thừa của một số nguyên tố |
| 4 | ~20\%~ | ~N~ là tích của hai lũy thừa của một số nguyên tố |
| 5 | ~20\%~ | Không có ràng buộc thêm |
Sample Input 1
10 2
1 5
5 10
Sample Output 1
2
2
Notes
Truy vấn 1: trong đoạn ~[1,5]~ có 2 số nguyên tố cùng nhau với 10 là 1 và 3.
Truy vấn 2: trong đoạn ~[5,10]~ có 2 số nguyên tố cùng nhau với 10 là 7 và 9.
Bình luận