---
# System prepended metadata

title: RPRIME Solution
tags: [RPRIME]

---

---
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)