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

Cho bốn số nguyên $a$, $b$, $p$, $x$ với $p$ là số nguyên tố. Hãy đếm số nguyên dương $n$ trong khoảng $[1,x]$ thoả phương trình:

• $$n·a^n\equiv b\left(\mathrm{mod}p\right).-$$

Dữ liệu vào

Một dòng duy nhất chứa bốn số nguyên $a$, $b$, $p$, $x$.

Dữ liệu ra

In ra một số nguyên — số lượng giá trị $n$ thoả mãn.

Ràng buộc

• $2\le p\le {10}^6+3$, $p$ là số nguyên tố.
• $1\le a,b<p$.
• $1\le x\le {10}^{12}$.

Ví dụ

Ghi chú

Gợi ý: theo định lý Fermat nhỏ, $a^{p-1}\equiv 1\left(\mathrm{mod}p\right)$, nên $a^n$ tuần hoàn theo $n$ với chu kỳ chia hết $p-1$. Kết hợp với điều kiện $n\left(\mathrm{mod}p\right)$, có thể dùng định lý số dư Trung Hoa (CRT) để tìm tập các nghiệm $n$ theo modulo $p(p-1)$.