题解 CF7C 【Line】

· · 题解

upd：on 2019.11.13，增加了L_A^TE_X语句，看起来舒服多了qwq

扩展欧几里得！！！

萌新刚学exgcd，来一波题解~

Q：这个算法叫什么名字？

A：扩展欧几里得，又称exgcd。

Q：讲一讲qwq？

A：我们先引入一条定理——

斐蜀定理：对任何a,b∈Z和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：ax+by=c有整数解(x,y)当且仅当d∣c，可知有无穷多解。特别地，一定存在整数x,y，使ax+by=d成立。

由裴蜀定理，我们可以得出一个小推论：

推论：a,b互质的充要条件是存在整数x,y使ax+by=1。

这里作者推荐一篇关于斐蜀定理的证明

A：好，那么对于方程ax+by=c，设d=gcd(a,b)，根据斐蜀定理可知ax+by=d一定有正整数解，怎么求解x,y呢？

我们注意到：欧几里德算法停止的状态是：a=d，b=0，此时当x=1,y=0(实际任意值都可以)时d*1+0*0=d成立，这是最终状态，我们根据这个最终状态反推出初始状态的值即为答案，怎么反推？

设x,y和x1,y1是两组解，且满足：

由  a*x+b*y=gcd(a,b)
    b*x1+(a%b)*y1=gcd(b,a%b)
得  a*x+b*y=b*x1+(a%b)*y1

设k=a/b,r=a%b,则r=a-k*b,代入上式得
    a*x+b*y=b*x1+(a-a/b*b)*y1
    a*x+b*y=a*y1+b*(x1-a/b*y1)
得  x=y1
    y=x1-a/b*y1

所以通过以下函数可以在求a,b的gcd的同时求出方程ax+by=d的一组特解

int exgcd(int a,int b)
{
    if(b==0){x=1;y=0;return a;}
    int tmp=exgcd(b,a%b);
    int t=x;
    x=y;y=t-a/b*y;
    return tmp;
}

现在已经求出了一组特解x_0,y_0，ax+by=d的通解又是什么？

直接给出：x=x_0+b/d*k，y=y_0-a/d*k，k为任意整数

为什么是这个？因为它带入ax+by=d等式成立。

那你会问，带入等式成立的多了，比如x=x_0+b*k，y=y_0-a*k，为什么非要选它？

因为它能无遗漏的表示所有整数解。

证明如下：

因为b/d是b的因子，所以x_0+b/d*k能取到的值比x_0+b*k多，同理y_0-a/d * k也是

设B=b/d,A=a/d，所以A,B互质，所以A,B为最小系数。

证毕。

好的，以上就是exgcd的基本定义及证明。

那么，我们可以用它干什么呢——

1、求解不定方程ax+by=c
2、求解线性同余方程
3、求解模的逆元

题目不会让你求出所有解，一般会限定条件，
比如某个区间内的解，最小正整数解等等

解不定方程ax+by=c

由斐蜀定理知当d|c时才有整数解

将方程两边同时除以gcd(a,b)，设a'=a/gcd(a,b)，

由扩展欧几里得定理知一定存在$x_0,y_0$使得$a'x_0+b'y_0=1$。 则可由$exgcd$求出$x_0,y_0$，将上式两边同时乘以$gcd(a,b)$得 $a'gcd(a,b)x_0+b'gcd(a,b)y_0=gcd(a,b)

==> ax_0+by_0=gcd(a,b)

==> ax_0+by_0=c/c'，

所以

x_1=x_0*c'=c/d*x_0$，$y_1=y_0*c=c/d*y_0

为方程的另一组解

则方程ax+by=c的通解为

x=x_1+b/d*k=c/d*x_0+b/d*k，y=y_1-a/d*k=c/d*y_0-a/d*k

解线性同余方程

对于线性同余方程：ax≡m(mod\ b)

ax$%$b=m

-> ax=by+m

-> ax-by=m

-> ax+by=m

乘法逆元

存在x使得ax≡1(mod\ p)，则称x的最小正整数解是a关于p的乘法逆元

定理：a关于p的乘法逆元存在的充要条件是gcd(a,p)=1

逆元有什么作用呢？


当要求(a/b)%p时，且a很大，我们就求b关于p的乘法逆元x，则有(a/b)%p = (a*x)%p

根据b*x≡1 (mod p)有b*x=p*y+1。

则x=(p*y+1)/b。

把x代入(a*x) mod p，得：
(a*(p*y+1)/b) mod p
=((a*p*y)/b+a/b) mod p
=[((a*p*y)/b) mod p +(a/b)] mod p
=[(p*(a*y)/b) mod p +(a/b)] mod p

//p*[(a*y)/b] mod p=0

代码如下：

好的，关于exgcd的用途也讲完了，那么我们回到

这道题——

很明显，这道题是让我们求Ax+By=-C的一组解，并且x,y∈[-5e18,5e18]。

所以说这是exgcd的一道裸题~

直接上代码吧——

#include<cstdio>
using namespace std;

long long a,b,c,x,y,d;//这道题要开long long！！！

int exgcd(int a,int b)//扩展欧几里得
{
    if(b==0){x=1;y=0;return a;}//临界条件
    int tmp=exgcd(b,a%b);//逆推回去求解
    int t=x;
    x=y;y=t-a/b*y;
    return tmp;
}

int main()
{
    scanf("%lld%lld%lld",&a,&b,&c);
    c=-c;
    int d=exgcd(a,b);
    if(c%d!=0){printf("-1\n");return 0;}//如果无解
    x=c/d*x;
    y=c/d*y;//这里是求出k=0时的通解
    printf("%lld %lld\n",x,y);
    return 0;//功德圆满
}
//CSP2019rp++

谢谢各位的观看~如果不介意的话顶一个再走吧qwq~