题目描述
有以下几个问题：
1 给定正整数 
求方程 
的最小非负整数解。
2 给定正整数 
求方程 
的最小非负整数解。
3 给定正整数 
求方程 
在模 
意义下解的数量。
4 给定正整数 
求 
的值。其中 
是欧拉函数， 
是莫比乌斯函数。
输入格式
输入文件共四行，按上述描述中四个问题的顺序，给出每个问题。
第一行三个正整数 表示第一个问题，保证 
。
第二行三个正整数 表示第二个问题，保证 
。
第三行三个正整数 表示第三个问题，保证 
为质数且 
。
第四行三个正整数 表示第四个问题。
输出格式
共四行每行一个整数，分别表示四个问题的答案。对于前两个问题，若问题无解则输出-1。对于第三个问题你只需输出解的数量。
样例数据
super.in
3 6 8
9 10 12
4 4 7
5 4 20
super.out
2
-1
2
4
数据范围
20% 的数据： 
60% 的数据： 
100% 的数据： 
评分方式
对于每个测试点:
• 第一个问题正确得 2 分。
• 第二个问题正确得 3 分。
• 第三个问题正确得 3 分。
题解
第一问：将式子化成 
, 拓展欧几里得即可。
第二问： BSGS大步小步算法解高次同余方程。
详情请见TonyFang博客：http://tonyfang.is-programmer.com/posts/178997.html
第三问：求出 的一个原根 
，可以求出 
，并设 
, 则由费马小定理可知，解该方程等价于解 
所以实际上它是前两个问题的组合应用。
第四问：Pollard Rho算法和Millar Rabin算法的应用。