Phương trình đồng dư

Hướng tiếp cận

Sử dụng định lý Fermat nhỏ và định lý số dư Trung Hoa (CRT) để rút gọn bài toán về một số $O(p)$ trường hợp dư rồi đếm theo công thức cấp số cộng.

Nhận xét quan trọng

1. Tuần hoàn của $a^n$: $gcd(a,p)=1$ nên $a^{p-1}\equiv 1\left(\mathrm{mod}p\right)$. Suy ra $a^n\left(\mathrm{mod}p\right)$ chỉ phụ thuộc $i=nmod(p-1)$.
2. Phương trình modulo $p$: cố định $i$. Khi đó $a^i$ là hằng số khả nghịch, nên $n\equiv b·(a^i{)}^{-1}(\mathrm{mod}p)$. Đặt $j=b·a^{-i}modp$.
3. CRT: với mỗi $i\in \{0,1,\dots ,p-2\}$, hệ:
   • $n\equiv i\left(\mathrm{mod}p-1\right)$
   • $n\equiv j\left(\mathrm{mod}p\right)$ có duy nhất một nghiệm $n_0\in [0,p(p-1))$. Lý do duy nhất: $gcd(p-1,p)=1$.

Thuật toán

1. Tiền tính $a^{i}modp$ cho $i=0,\dots ,p-2$. Nghịch đảo của $a^i$ là $a^{p-1-i}$.
2. Đặt $g=p(p-1)$. Với mỗi $i$:
   • Tính $j=b·a^{-i}modp$.
   • Tìm $k=(i-j)modp$ (vì $p-1\equiv -1\left(\mathrm{mod}p\right)$).
   • Đặt $n_0=i+(p-1)·k$. Nếu $n_0=0$ thì lấy $n_0=g$ (vì $n\ge 1$).
   • Nếu $n_0\le x$, cộng $\lfloor (x-n_0)/g\rfloor +1$ vào đáp án.
3. In tổng.

Độ phức tạp

• Thời gian: $O(p)$.
• Bộ nhớ: $O(p)$ cho bảng luỹ thừa.