#H1006. 【模板】Pohlig Hellman

【模板】Pohlig Hellman

题目描述

给定一个质数 pp,以及一个整数 bb,一个整数 nn,现在要求你计算一个最小的 ll,满足 bln(modp)b^l\equiv n \pmod p

输入格式

仅一行,有 33 个整数,依次代表 p,b,np,b,n

输出格式

仅一行,如果有 ll 满足该要求,输出最小的 ll,否则输出 1-1

5 2 3
3

样例解释

23mod5=32^3\bmod 5=3

数据规模与约定

对于 100%100\% 的数据,2b,n<p<10182\leq b,n<p<10^{18},保证 p1p-1 仅有 2,32,3 两个本质不同的质因子。