solution

Chọn ngẫu nhiên, độc lập và đồng khả năng hai số nguyên $X$ và $Y$ trong tập $\{1, 2, \dots, N\}$ (có thể $X=Y$). Hãy tính xác suất $P(\gcd(X,Y) = 1)$, tức là xác suất hai số được chọn nguyên tố cùng nhau.

Không gian mẫu có $N^2$ cặp $(X,Y)$ đồng khả năng. Sử dụng hàm Mobius $\mu$, số cặp nguyên tố cùng nhau được tính chính xác bằng công thức:

$\#\{(x,y): \gcd(x,y)=1\} = \sum_{k=1}^{N} \mu(k) \left\lfloor \frac{N}{k} \right\rfloor^2$

Lưu ý $N$ có thể lớn (đến $2\times10^5$), nên không được duyệt trực tiếp tất cả $N^2$ cặp; cần thuật toán hiệu quả (ví dụ sàng tính $\mu(k)$ với độ phức tạp $O(N)$ hoặc $O(N\log\log N)$ rồi áp dụng công thức trên).

Ví dụ: $N=2$: các cặp là $(1,1),(1,2),(2,1),(2,2)$, trong đó $\gcd=1$ ở ba cặp đầu, cặp $(2,2)$ có $\gcd=2$. Vậy $P = 3/4$.