信息学奥赛题库- 计算器

【题目描述】

这是一道计算题，你需要计算下面三个算式的值：

(1)给定$P,y,z$，求$y^zbmod P$。

(2)给定$P,y,z$，求满足$y^x≡z(bmod P)$的最小非负整数解。

(3)给定$P,y,z$，求$C_z^ybmod P$，其中$C_z^y$为$z$中取$y$的组合数。

【输入】

第一行一个整数$N$表示数据组数。

接下来$N$行每行四个整数$type,y,z,P$。$type$表示询问类型，保证$type∈{1,2,3}$。

【输出】

对于每组数据输出一行表示答案。对于问题类型（2）若$x$不存在则输出“Math Error”（不含引号）。

【输入样例】

6
2 2 3 4
3 2 7 9
2 1 2 9
3 1 6 7
1 5 3 7
1 9 2 8

【输出样例】

Math Error
3
Math Error
6
6
1

【提示】

【数据规模与约定】

对于100%的数据，若$P$不为质数，且$P = prod_{i=1}^{k}P_{i}^{a_i}$ ，其中$p_i$是互不相同的质数，保证 $P_i^{a_i}≤10^5$ 。