扩展欧几里得求乘法逆元

void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(!b){d=a; x=1; y=0;}
	else { ex_gcd(b,a%b,d,y,x); y-=x*(a/b);}
}
ll inv(ll a,ll p){//求a关于p的逆元 即除以a%p相当于乘以多少%p
	ll d,x,y;
	ex_gcd(a,p,d,x,y);
	return d==1?(x+p)%p:-1;	
}