#P2485. [SDOI2011] 计算器

    ID: 1493 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2011各省省选山东O2优化素数判断质数筛法最大公约数gcd逆元

[SDOI2011] 计算器

题目描述

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

  1. 给定 y,z,py,z,p,计算 yzmodpy^z \bmod p 的值;
  2. 给定 y,z,py,z,p,计算满足 xyz(modp)xy \equiv z \pmod p 的最小非负整数 xx
  3. 给定 y,z,py,z,p,计算满足 yxz(modp)y^x \equiv z \pmod p 的最小非负整数 xx

为了拿到奖品,全力以赴吧!

输入格式

输入文件包含多组数据。

第一行包含两个正整数 T,KT,K,分别表示数据组数和询问类型(对于一个测试点内的所有数据,询问类型相同)。

以下 TT 行每行包含三个正整数 y,z,py,z,p,描述一个询问。

输出格式

输出文件包括 TT 行。

对于每个询问,输出一行答案。

对于询问类型 2 和 3,如果不存在满足条件的,则输出 Orz, I cannot find x!

3 1
2 1 3
2 2 3
2 3 3
2
1
2
3 2
2 1 3
2 2 3
2 3 3
2
1
0
4 3
2 1 3
2 2 3
2 3 3
2 4 3
0
1
Orz, I cannot find x!
0

提示

测试点共分为三类,各类测试点占总测试点的比例如下:

K=K= 测试点占比
11 20%20\%
22 35%35\%
33 45%45\%

所有数据均满足:1y,z,p1091 \leq y,z,p \leq 10^9pp 是质数,1T101 \leq T \leq 10