--- author: little tags: RPRIME title: RPRIME Solution --- $\Huge\text{RPRIME Solution}$ ------- :::info 🔗 Links: [Đề bài](https://drive.google.com/file/d/1f4hP29jX8hDwGcwVxvApTCxS0Qf61v5R/view?usp=sharing) 📌 Tags: `implementation` `inclusion - exclusion` `math` ✍️ Writer: little 📋 Content: [TOC] ::: ----- ## Tóm tắt đề bài Cho số nguyên $N$ và $m$ cặp số $a, b$. Với mỗi cặp $a, b$, hãy in ra số lượng số nguyên tố cùng nhau với $N$ trong đoạn $[a, b]$. ----- ## Thuật toán Thay vì ta đếm số lượng số nguyên tố cùng nhau với $N$ trong đoạn $[a, b]$, ta sẽ đếm số lượng số không nguyên tố cùng nhau với $N$ tức là các số mà ước chung lớn nhất của nó và $N$ khác $1$. Ta đếm số lượng số không nguyên tố cùng nhau với $r$ bằng bao hàm loại trừ như sau: - Xét các ước nguyên tố của $N$, để chúng vào một mảng, tạm gọi là mảng $pos$. - Ta sẽ chạy qua mọi cách ghép của mảng $pos$, có $2 ^ {pos.size()}$ cách ghép, với mỗi trạng thái ghép ta sẽ có được tích của các $pos[i]$ mà các $bit$ ở vị trí $i$ đều được bật. - Sau đó ta tính được số lượng số trong đoạn $[1, r]$ chia hết cho $pos[i]$ bằng công thức $\frac{r} {pos[i]}$, tạm gọi đó là $cur$. - Nếu như số lượng $bit$ được bật của trạng thái hiện tại là lẻ thì ta cộng $cur$ vào kết quả, còn nếu số lượng $bit$ được bật của trạng thái hiện tại là chẵn thì ta trừ $cur$ vào kết quả. Xem chứng minh ở [Bao hàm - loại trừ](https://vnoi.info/wiki/translate/he/Number-Theory-7.md). ---- Tham khảo code ở [đây](https://ideone.com/4AvpL4)