同余方程exgcd板子

a*x1+b*y1=gcd(a,b) 是由 b*x2+（a%b）y2=gcd（b，a%b）推导来的；

so   

       a*x1+b*y1= b*x2+（a%b）y2  

       a*x1+b*y1=b*x2+（a-a/b*b）y2

       a*x1+b*y1=b*x2+a*y2-a/b*b*y2

       a*x1+b*y1=a*y2+b（x2-a/b*y2）

so

        x1=y2      y1=x2-a/b*y2

上网随便找的一个exgcd推导，推导只是帮助理解，重点在于代码，记忆力强大的，背会直接应用就好QAQ

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