2017.10.29闵神讲课DAY2（数论）

模运算

等大家刷题刷的多了，就会发现一些题会要求你对最终答案对P取模（当然也会有一些**的题目会让你高精度，不谈了）

除法定理

对于一个整数x和正整数p，x能被唯一地表示为x=a*p+b，其中a是整数,b是小于p的非负数.
这个小学学过吧，a是x除以p的商，b是余数。
x对p取模的结果自然是b，如果有另一个数y=c*p+d，首先y模p的结果就是d，那么这两个数如果做一些运算答案对p取模的结果是什么呢？
下面推一些公式，不是很难。

加减乘…..

继续沿用刚才x和y的定义:

x±y=(a±b)p+(c±d)，设c±d=e*p+f，那么
x±y=(a±b+e)p+f，所以(x±y)%p=(c±d)%p
x*y=(a*c)*p^2+(b*c+a*d)*p+(c*d)，设c*d=e*p+f
那么xy=(a*c*p+b*c+a*d+e)*p+f，(xy)%p=(cd)%p
这个说明了什么呢？不管x和y本身是多少，他们运算后模p的结果就是他们模p后运算的结果再模p，求解时只需要保留过程中的数模p的结果就行

定义运算

有了这个性质我们就可以把程序中所有需要操作的数都限定到[0,p-1]范围内辣。
思考：如果数刚开始不是这个范围内咋办？
下面是闵神的模板，注意细节和常数的处理。

也就是举个例子
如果题目要你%2333（这是一个质数）

那么在这个题目中2334等价于1
4666等价于0
就是2334=1，,4666=0在此题是正确的
这样我们就可以避免很多大数据的计算

乘法逆元

在此我们需要引进两个新的概念：
单位元：单位元(英文常写作Identity Element，即IE)是集合里的一种特别的元，与该集合里的运算（可理解为实数里的*，但并不局限于）有关。当它和其他元素结合时，并不会改变那些元素。（说的通俗一点，加法的单位元就是0,；乘法的单位元就是1）
逆元：逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。

对于除法来说，同余原理是不满足的（即（a/b）%p！=（a%p）/（b%p））

那么我们该怎么处理除法呢？？

这时候我们就要用到逆元了！
将除法转化为乘这个数的逆元

定义：对于正整数a和m，如果a*x mod m=1, 则x的最小正整数解称为a模m的逆元，表示为a^(-1) （mod m）

求解方法：（1）根据费马小定理：有a^(m-1) mod m=1, 即a*a^(m-2) mod m=1, 所以a^(m-2)就是a模m的逆元。 （适用条件：m为素数）

　　　　　（2）扩展欧几里得求解：a*x mod m=1,即a*x-m*y=1,解这个丢番图方程即可。 (适用条件：gcd(a,m)=1)

　　　　　（3）欧拉函数法：留个坑。

　　　　　（4）线性递推：规定m为质数，且1^(-1)≡1(mod m) 设$m=k∗a+b (b < a,1<a<m)$， 即 k∗a+b≡0(mod m)

　　　　　　　　　　　　 两边同时乘以a^(−1)∗b^(−1)，得到:
　　　　　　　　　　　　 k∗b(−