本文主要向大家介绍了C/C++知识点之【NOIP训练】【数论】超级计算机，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

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

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！