同余定理：
    按字面意思来理解，就是两个数除以同一个数m余数相同；
    举个栗子：100%8=4；60%8=4；那么就可以说，100与60对8取模相同，记作：100≡60（mod 8）；

逆元：

    如果两个数a和b，a*b对于数m取余和1对m取余相等，即：（a*b）≡1(mod m);就称，b是a的逆元。
    反之，如果已知一个数c是数字b的逆元，即有：（b*c）≡1（mod m）;

如何求一个数的逆元：

根据费马小定理求逆元：

    费马小定理：如果p是质数，且数字a与p互质，那么，a^（p-1）≡1(mod p)；
    这里有两个条件：1，p必须是质数;2，a不能被p整除。   结论就是，a的p-1次方对p求余等于1；
    那么接下来：
        a^（p-1）≡1(mod p)
        a*a^(p-2)≡1(mod p)
        所以，在满足条件的情况下，a的逆元就是a^(p-2);只需要用快速幂求一下a的p-2次方。

根据扩展欧几里得求逆元：

贝足定理：

        如果a,b为整数，那么一定存在x，y使得ax+by=gcd(a,b);
    换句话说，就是方程ax+by=m有解，那么m一定是gcd(a,b)的若干倍；
    另，若ax+by=1有解，那么gcd(a,b)=1;

欧几里得算法：

     欧几里得有一个定理：gcd(a,b)=gcd(b,a%b);也就是辗转相除法，求gcd.
辗转相除法：       

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
扩展欧几里得算法： 

#include<iostream>
#include<cstdio>
#include<cmath>
 
using namespace std;
 
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    int r=exgcd(b,a%b,x,y);
    int temp=y;    //把x y变成上一层的
    y=x-(a/b)*y;
    x=temp;
    return r;     //得到a b的最大公因数
}

 当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解：a*1+b*0=gcd(a,b)，x=1,y=0

扩展欧几里得求逆元：
    a*x≡1(mod m) 等价于a*x+m*y=1可以用扩展欧几里得求得一组解，（x+m）mod m 即为a的逆元。 

int cal(int a,int b)
{
	int x,y;
	int gcd=exgcd(a,m.x.y);
	if(1%gcd!=0) return -1;
	x*=1/gcd;
	m=abs(m);
	int ans=x%m;
	if(ans<=0) ans+=m;
	return ans;
}