模板2

求解形如Ax≡B(mod M)的最小正整数解。

il void exgcd(re ll A,re ll B,re ll &D,re ll &x,re ll &y)
{
  if(!B) x=1,y=0,D=A;
  else exgcd(B,A%B,D,y,x,c),y-=(A/B)*x;
}
il void solve2()
{
  re ll A=atk[1],B=a[1],M=p[1],D,x,y,ysn,zsy;
  exgcd(A,M,D,x,y);//D=gcd(A,M)
  if(B%D) {puts("-1");return;}
  x=x*(B/D)%(M/D);
  printf("%lld
",x);
}