题解 CF7C 【Line】
fls233666
2020-11-29 22:57:42
首先我们从这个直线方程入手：
$$
Ax+By+C=0
$$
也许我们并不能从这个普通的直线方程里面看出什么。
但如果移项一下：
$$
Ax+By=-C
$$
好极了！现在这是**一个标准的二元一次不定方程**了！
下面我们考虑哪些数论知识和二元一次不定方程有关。
一般，我们会最先想到的两个定理，就是 [裴蜀定理](https://oi-wiki.org/math/bezouts/) 和 [扩展欧几里得定理](https://oi-wiki.org/math/gcd/) 。
为什么呢？
先简单说明一下这两个定理分布有什么用处。
- 裴蜀定理：用于判定一个一元二次不定方程是否有整数解。
- 扩展欧几里得定理：用于求出一个有整数解的一元二次不定方程 $ax+by=\gcd(a,b)$ 的一组可行解。
而再看题目要我们做的事情：
- 判断直线上是否存在整点。
- 如果有整点，找到并输出一个整点。
正好和我们用这两个定理能做的事情一致！
下面开始介绍具体做法。
首先说明一下裴蜀定理的具体内容：
**对于一个一元二次不定方程 $ax+by=c$ ，它有整数解，当且仅当 $c$ 能够被 $\gcd(a,b)$ 整除。**
由此，判断 $C$ 是否能被 $\gcd(A,B)$ 整除，即可得到是否有解。
有解之后，再使用扩展欧几里得定理，我们可以求得一组关于方程 $Ax+By=\gcd(A,B)$ 的可行解。记这组可行解为 $x_0,y_0$。因为我们真正要求解的方程是 $Ax+By=-C$ ，所以最终答案为 $x=x_0 \times \frac{-C}{\gcd(A,B)},y=y_0 \times \frac{-C}{\gcd(A,B)}$
思路大致如上，下面就是代码：
```cpp
#include<iostream>
#include<cstdio>
#define ll long long
#define rgt register int
using namespace std;
ll a,b,c,x,y,g;
ll exgcd(ll num1,ll num2){ //标准的EXgcd
if(!num2){
x=1;
y=0; //ax+by=a的一个可行解
return num1; //返回最大公约数
}
ll tg=exgcd(num2,num1%num2); //辗转相除
ll tmp=x;
x=y;
y=tmp-y*(num1/num2); //转化可行解
return tg; //返回最大公约数
}
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
g=exgcd(a,b);
if(c%g) //由裴蜀定理判无解
printf("-1");
else{ //求出题目要的答案
x*=c/g;
y*=c/g;
printf("%lld %lld",-x,-y);
}
return 0;
}
```