非质数取模求逆元模板

不想复习扩展欧几里得了,万年不考的东西...也没太多用..

inline int exgcd(int a,int b,int& x,int& y) 
{
    if(!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,x,y);
    int z=x; x=y; y=z-a/b*y;
    return d;
}

inline int inv(int a,int m)//a在mod m意义下的逆元
{ 
    int x,y,d=exgcd(a,m,x,y);
    return d==1?(x%m+m)%m:-1;
}