$k$ 是啥?
by zhouyuhang @ 2022-05-14 18:03:03
k指c ~~。。。。。。~~
by hbhz_zcy @ 2022-05-14 18:03:53
这对才有鬼了吧。是 $\gcd(a, b)\mid c$ 又不是 $a\mid c$。。
by zhouyuhang @ 2022-05-14 18:05:20
@[zhouyuhang](/user/314991) 好吧我又看错了,把源码放上来
```cpp
LL exgcd(LL a,LL b,LL &x,LL &y,LL k){
if(!b){x=k/a,y=0;return {k%a?-1:a};}
LL rt=exgcd(b,a%b,x,y,k),x0=x;
x=y,y=x0-a/b*y;
return rt;
}
```
非常抱歉
by hbhz_zcy @ 2022-05-14 18:09:59
-1是个调试
by hbhz_zcy @ 2022-05-14 18:10:19
@[38432386zcy](/user/142549) 我仔细看了一下您的代码。注意到您 ```exgcd``` 最后的 $a$ 实际上就是一开始的 $\gcd(a, b)$,因此在一般情况下不会有问题。我猜测可能您没有处理好 $\gcd(a,b)\nmid c$ 的情况。虽然您特判了 ```k % a ? -1 : a```,但是这里的 ```-1``` 在返回的过程中值会发生改变。因此建议您在主函数中加入
```cpp
if(c % exgcd(a, b, x, y, c)) cout << -1 << endl;
else cout << x << ' ' << y << endl;
```
这类语句。
by zhouyuhang @ 2022-05-14 18:23:51
另外附一下证明吧,其实就是你直接 ```exgcd``` 是求 $ax+by=\gcd(a,b)$ 的一组解 $(x_0,y_0)$;而您这个相当于令 $x=\frac{c}{\gcd(a,b)}x_0,y=\frac{c}{\gcd(a,b)}y_0$,这在 $\gcd(a,b)\mid c$ 时当然是对的。
by zhouyuhang @ 2022-05-14 18:31:05
非常感谢
by hbhz_zcy @ 2022-05-14 18:36:52