Truy vấn nguyên tố cùng nhau
Xem dưới dạng PDFCho số nguyên \(n\). Có \(q\) truy vấn dạng \((l,r)\), đếm số lượng số nguyên trong đoạn \([l,r]\) nguyên tố cùng nhau với \(n\) \((UCLN(n,x)=1)\).
Dữ liệu vào
- Một dòng gồm \(2\) số nguyên \(n,q\).
- \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(l,r\), một truy vấn.
Ràng buộc
- \(1 \le n,l,r \le 10^{12}\).
- \(1 \le q \le 10^4\)
Dữ liệu ra
- In ra đáp án cho mỗi truy vấn.
Input 1
10 2
1 5
5 10Output 1
2
2
Nhận xét
Hehe, Rock thập niên 90 là chân lý UwU