← 返回题目列表

Codeforces · 919/E

E. 同余方程

中文机器翻译题面 查看原题

给定一个整数 $$$x$$$。你的任务是找出有多少个正整数 $$$n$$$ ($$$1 \leq n \leq x$$$) 满足 $$$$$$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$$$$$ 其中 $$$a, b, p$$$ 都是已知常数。

输入

唯一的一行包含四个整数 $$$a,b,p,x$$$ ($$$2 \leq p \leq 10^6+3$$$, $$$1 \leq a,b < p$$$, $$$1 \leq x \leq 10^{12}$$$)。保证 $$$p$$$ 是素数。

输出

打印一个整数:可能的答案 $$$n$$$ 的数量。

示例

输入 #1

2 3 5 8

输出 #1

2

输入 #2

4 6 7 13

输出 #2

1

输入 #3

233 233 10007 1

输出 #3

1

注意

在第一个示例中,我们可以看到 $$$n=2$$$ 和 $$$n=8$$$ 是可能的答案。