首页 > > 程序设计 > C/C++ >

【NOIP训练】【数论】超级计算机

2018-06-17 23:51:02来源：未知阅读 ()

题目描述
有以下几个问题：
1 给定正整数求方程 $ax\,$\equiv$\,b\,(mod$\quad$c)$ 的最小非负整数解。
2 给定正整数求方程 $g^x\,$\equiv$\,f\,(mod$\quad$h)$ 的最小非负整数解。
3 给定正整数求方程 $x^u$\equiv$v(mod$\quad$w)$ 在模意义下解的数量。
4 给定正整数求 $(\phi(x)+\mu(y))$\quad$mod$\quad$z$ 的值。其中 $\phi(x)$ 是欧拉函数， $\mu(y)$ 是莫比乌斯函数。
输入格式
输入文件共四行，按上述描述中四个问题的顺序，给出每个问题。
第一行三个正整数表示第一个问题，保证 a,b<c 。
第二行三个正整数表示第二个问题，保证。
第三行三个正整数表示第三个问题，保证为质数且。
第四行三个正整数表示第四个问题。
输出格式
共四行每行一个整数，分别表示四个问题的答案。对于前两个问题，若问题无解则输出-1。对于第三个问题你只需输出解的数量。
样例数据
super.in
3 6 8
9 10 12
4 4 7
5 4 20

super.out
2
-1
2
4
数据范围
20% 的数据： $a,b,c,f,g,h,u,v,w$\leq$20$
60% 的数据： $x,y,z$\leq$230$
100% 的数据： $a,b,c,f,g,h,u,v,w$\leq$230;x,y,z$\leq$260$
评分方式
对于每个测试点:
? 第一个问题正确得 2 分。
? 第二个问题正确得 3 分。
? 第三个问题正确得 3 分。

题解

第一问：将式子化成 ax+cy=b , 拓展欧几里得即可。

第二问： BSGS大步小步算法解高次同余方程。

详情请见TonyFang博客：http://tonyfang.is-programmer.com/posts/178997.html

QQ截图20160829192019

第三问：求出的一个原根，可以求出 $p^b\,$\equiv$\,v(mod$\quad$w)$ ，并设 $p^a\,$\equiv$\,x(mod$\quad$w)$ , 则由费马小定理可知，解该方程等价于解 $au$\equiv$b(mod$\quad$w-1)$ 所以实际上它是前两个问题的组合应用。