#P9339. [TJOI2007] 可爱的质数/【模板】

    ID: 5727 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-BSGS费马小定理模逆元快速幂哈希表难度分类

[TJOI2007] 可爱的质数/【模板】

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5 2 3

样例输出 #1

3

提示

数据规模与约定

  • 对于所有的测试点,保证 2≤b,n<p<2312\le b,n < p<2^{31}。