题解 P1082 【同余方程】

感觉还没有人讲到为什么是exgcd(x,y,a,b)而不是exgcd(x,y,a,-b) 如果又是我看漏了的话..反正题解是写给自己看的 ------------ 错误思路： 由ax ≡ 1 (mod b)得ax=by+1 移项得：ax-by=1 于是天真的我一开始写的exgcd(x,y,a,-b)，各种WA ------------ 先讲为什么可以exgcd(x,y,a,b)： 其实一句话就可以说明，令y'=-y，ax+by'=ax-by，而本题只求x ------------ 然后是为什么不能exgcd(x,y,a,-b)： 因为这题是基于gcd(a,y的系数（正解中的b，错解中的-b）)=1的 而gcd(a,b)当b为负数时，可以举例看一下 gcd(12,-7)=gcd(-7,5)=gcd(5,-2)=gcd(-2,1)=gcd(1,0)=1 gcd(17,-5)=gcd(-5,2)=gcd(2,-1)=gcd(-1,0)=-1 可以看出，结果是1还是-1和gcd次数的奇偶有关，因此会出现大量WA ------------ 总结：使用exgcd时要注意a,b为正，求解ax=by+1（a,b为互质正整数）的解集时，要先求出ax+by=1的解集A'，那么所求解集即为A{(x,y)|(x,-y)∈A'} ------------ 毕竟是题解..还是给份完整代码 ``` #include <iostream> using namespace std; void exgcd(int& x,int& y,int a,int b); int main() { int a,b,d,x,y,k; cin>>a>>b; exgcd(x,y,a,b); while (x<0) { x+=b; } cout<<x%b; return 0; } void exgcd(int& x,int& y,int a,int b) { if (b==0) { x=1; y=0; } else { exgcd(y,x,b,a%b); y-=a/b*x; } } ```