请使用$L^{A_T}E_X$，谢谢
by AThousandSuns @ 2018-04-15 14:32:51
@[AThousandSuns](/space/show?uid=72118) ？？
by jtzhang @ 2018-04-15 14:35:52
下面引用一下“caoyu ”的推论：
------------
------------
目标解AX+BY==C
有解的条件是C%gcd（A，B）==0
那么也就是C==Kgcd（A，B），K∈Z
那么就办成了AX+BY==Kgcd（A，B）
那么也就是解A（X/K）+B（Y/K）==gcd（A，B）
然后扩展欧几里得定理就是解AX+BY==gcd（A，B）
那么解出来X之后X就要乘上K也就是要乘上C/gcd（A，B）
设Z=C/gcd（A，B）
那么为了防止输出负数，ans=（(XZ)%P+P）%P
------------
------------
根据“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==Kg 推出 K=C/g
**即“caoyu”所说的“ans=（(X*Z)%P+P）%P”
中的P=B/g*C/g**
**而题解上全部给的是P=B/g**
by jtzhang @ 2018-04-15 14:40:49
不用了，我想明白了
：
得出 aX+bY=gcd(a,b)后
再根据《算法竞赛——入门经典》p313 提示10-1
X‘=X+b/gcd(a,b)
by jtzhang @ 2018-04-15 15:14:15
https://blog.csdn.net/garfielder007/article/details/51646604
by Rye_Catcher @ 2018-05-05 17:43:30