int64_t externGcd(int64_t a, int64_t b) {
   int64_t t = 0;
   while ((t*b + 1) % a != 0) {
      t += 1;
   }
   return (t*b + 1) / a;
}

这样不就直接计算出结果了么? 对于a*x+b*y=1有解: [x1]=k*b+1/a [y1]=-k*a 将k=t/a [x1]=(t*b+1)/a [y1]=-t 这里只需要知道[x1]>0的第一个整数就可以. 不知道错在哪里了...