题解 CF7C Line

虽然我在洛谷上没过

但是，我在CF上过了（滑稽

题目大意

给方程 (Ax+By+C=0).其中(A)，(B)，(C)为已知,求(x)，(y)。

Idea

拓展欧几里得算法的模板题.

该算法求出线性方程(Ax + By = gcd(A, B))

然后，这个方程可进行转换:

[Ax + By = gcd(A, B) ]

[ o Ax + By = -frac{C}{z}, -frac{C}{z}= gcd(A, B) ]

[ o Axast z + Byast z = C. ]

其中(x), (y)可以通过拓展欧几里得算法求出，

然后，我们只需要求出(z)， 而(z=-frac{C}{gcd(A,B)});

所以， 最终答案(x=xast -frac{C}{gcd(A,B)}) , (y=yast -frac{C}{gcd(A,B)});

---

以下给出拓展欧几里得的模板

inline int ecgcd(int a,int b,int &x,int &y){
	if(!b) {x=1; y=0; return a;}
	int d=exgcd(b,a%b,x,y);
	int z=x; x=y; y=z-y*(a/b);
	return d;
}

(AC) 程序自己写