1、快速幂

计算a^b的快速算法，例如，3^5，我们把5写成二进制101，3^5=3^1*1+3^2*2+3^4*1

1 ll fast(ll a,ll b){ll ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a);return ans;}//一行快速幂

View Code

2、快速乘

当模数较大时，直接乘会爆掉long long,需要快速乘法。

即用浮点计算倍数，做差相当于计算余数模2^63的结果，然后再模一下就好了（因为余数不超过long long）

1 typedef long long ll;
2 ll mul(ll x,ll y){return ((x*y-(ll)(((long double)x*y+0.5)/mod)*mod)%mod+mod)%mod;}//一行快速乘

View Code

3、同余原理（gcd）

定理：gcd(a,b)=gcd(b,a mod b)

证明：a可以表示成a=kb+r，则r=a mod b 

　　   假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r ，因此d是(b,a mod b)的公约数

　　   假设d 是(b,a mod b)的公约数，则 d|b , d|r ，而a=kb+r，因此d也是(a,b)的公约数

　　   因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

1 int gcd(a,b){return !b?a:gcd(b,a%b);}//一行gcd

View Code

4、丢番图方程

裴蜀定理：丢番图方程（二元一次，下同）ax+by=m有解当且仅当m|(a,b)

扩展gcd：求丢番图方程ax+by=gcd(a,b)的整数解

证明：a*x1+b*y1=gcd(a,b)

　　　b*x2+(a mod b)*y2=gcd(b,a mod b)

　　   因为gcd(a,b)=gcd(b,a mod b)

　　　得a*x1+b*y1= b*x2+(a mod b)*y2 = b*x2+(a-a/b*b)*y2 = a*y2+b*(x2-a/b*y2)

　　　所以x1=y2,y1=x2-a/b*y2

末状态：b=0,a=gcd(a,b)时，gcd(a,b)*x=gcd(a,b),得x=1

扩展欧几里得的过程可以理解为从末状态向上不断回溯的过程，直到得到原方程的一组解。

1 void exgcd(int a,int b,int &x,int &y)
2 {
3     if(b==0)  {x=1; y=0; return;}
4     exgcd(b,a%b,x,y);
5     int t=x;x=y;y=t-a/b*y;
6 }

View Code

丢番图方程的通解：若(a,b)=d, ax+by=m有一组解(x0,y0)通解为：x=x0+(b/d)k, y=y0-(a/dk)就是设法让正负相互对消，（真·小学奥数内容）

解惑:多数初学者可能会有这样的疑问（反正我刚学的时候有），要解的方程是ax+by=m,而以上算法解的是ax+by=gcd(a,b)

其实ax+by=gcd(a,b)可以变为ax*k+by*k=gcd(a,b)*k,令gcd(a,b)*k=m,求出k，然后x*k就是ax+by=m的解。

5、乘法逆元

留个坑

6、中国剩余定理

留个坑

参考文献——王梦迪河南省队培训讲稿《数论基础》

数论知识总结——史诗大作（这是一个flag）