如题

设本题方程为

$a^x\equiv b\pmod m$

设EXBSGS的式子如下

$a^{x-y}\equiv(\frac {a^y}D)^{-1}\frac bD\pmod\frac mD$

本题缺少$x<y$的的数据。

原OJ SPOJ3104的数据比本题强。不判断$x<y$的代码可以通过此题，而不能通过SP3104

建议管理员增强数据

下面给出构造方法

$x<y$的数据等价于构造数据

分解

$a=\prod p_k^{c_{a,k}},m=\prod p_k^{c_{m,k}}$

由于

$y=\max\{\Big\lceil\frac {c_{m,k}}{c_{a,k}}\Big\rceil|c_{a,k}>0\}$

只需随机生成$a,m$，以上式计算$y$，构造$b$使得

$b=a^x\bmod m\quad s.t.\quad x<y$

即可

下面是我手造的一组hack数据

2 4 2
12 54 36
45 375 150
4 32 16
0 0 0