Description:


你被要求设计一个计算器完成以下三项任务:

  1. 给定 \(y,z,p\) ,计算 \(y^z \mod p\) 的值;
  2. 给定 \(y,z,p\) ,计算满足 \(x\times y \equiv z \pmod p \) 的最小非负整数 \(x\)
  3. 给定 \(y,z,p\) ,计算满足 \(y^x \equiv z \pmod p\) 的最小非负整数 \(x\)

Input:


输入包含多组数据。
第一行包含两个正整数T,K分别表示数据组数和询问类型(对于一个测试点内的所有数据,询问类型相同)。
以下行每行包含三个正整数y,z,p,描述一个询问。

Output:


对于每个询问,输出一行答案。对于询问类型2和3,如果不存在满足条件的,则输出“Orz, I cannot find x!”,注意逗号与“I”之间有一个空格。

Sample Input:


Sample Output:


Hint:


对于100%的数据, \(1\le y,z,p\le 10^9\)\(p\) 为质数, \(1\le T\le 10\)

题解:


之前一直不会BSGS,觉得名字特别厉害都不敢去看……

貌似乎也不是那么难。

对于第一种任务,直接快速幂;

对于第二种任务,把式子变形成 \(y\times x - k\times p = z\) ,然后用扩展欧几里得;

对于第三种任务,利用Baby Step Giant Step算法:
根据费马小定理, \(a^{p-1} \equiv 1 \pmod p\)
所以 \(0\le x \lt p-1\)
然后为了减少枚举的规模,我们可以设 \(m=\lceil \sqrt p \rceil\)
\(x\) 可以拆成 \(i\times m + j\) ,其中 \(0\le i, j\le m\)
那么 \(y^{i\times m + j} \equiv z \pmod p\)
然后就有 \(y^j\equiv z\times y^{-mi}\pmod p\)

所以我们可以考虑枚举左边的 \(j\) ,把左边所有的可能的值求出,然后枚举 \(i\) ,查找是否有相等的,即可以求出 \(x\)

代码如下:

 

好巧啊,刚写完博客第二天就考了 [摊手]