其实我也不知道
by xun薰 @ 2017-08-25 20:58:57
本人蒟蒻一名，刚刚试着理解了一下，如果不对的话请求不要吐槽......
目标解AX+BY==C
有解的条件是C%gcd（A，B）==0
那么也就是C==K\*gcd（A，B），K∈Z
那么就办成了AX+BY==Kgcd（A，B）
那么也就是解A\*（X/K）+B（Y/K）==gcd（A，B）
然后扩展欧几里得定理就是解A\*X+B\*Y==gcd（A，B）
那么解出来X之后X就要乘上K也就是要乘上C/gcd（A，B）
设Z=C/gcd（A，B）
那么为了防止输出负数，ans=（(X\*Z)%P+P）%P
by __Aurora_ @ 2017-11-08 19:55:27
鼓掌！！
by DoctorBobo @ 2018-01-22 14:18:02
我觉得有问题：
根据“caoyu ”的说法
1）C==K*gcd（A，B），K∈Z
2）A*（X/K）+B（Y/K）==gcd（A，B）
令g=gcd（A,B)
那么->它的下一个解就是（X/K+B/g) -- ——根据《算法竞赛——入门经典》p313 提示10-1
令下一个答案为X'
则
X’=X/K+B/g
X'=(X/K+B/g)*K
X'=X+B/g*K
X'=X+B/g**C/g ------根据1）C==K*g 推出 K=C/g
即“caoyu”所说的“ans=（(X*Z)%P+P）%P”
中的P=B/g*C/g
而题解上全部给的是P=B/g
by jtzhang @ 2018-04-15 14:22:22