题解P1082【同余方程】 (扩展欧几里得算法)

2018-04-30 18:55:48


扩展欧几里得

问题:求ax+by=c的一组解,设d=gcd(a,b),则d|ax,d|by,所以d|ax+by,所以如果有解,则d|c。如果c不整除于d,则原方程无解。

我们于是证明了d|c,所以原方程可以转化为求ax'+by'=d的解,则x=x'·c/d,y=y'·c/d。

因为gcd(a,b)=gcd(b,a%b)=d,所以我们想到了从bx'+(a%b)y'=d推到ax+by=d。而a%b=a-[(a/b)]·b,所以:bx'+(a%b)y'=d -> bx'+[a-[(a/b)]·b]y'=d -> ay'+b(x'-[a/b]·y')=d

SO~.... x=y',y=x'-[a/b]·y'

所以我们可以一直递归下去,直到b=0,此时求出了d=此时的a,也可以知道此时x=1,y=0,因为1·a+0·0=d。由这个状态,我们可以推出前面所有的x和y。于是我们就求出了ax+by=d的解。也知道了ax+by=c的解。

OK,看一下代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a,b,c,d;
void gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        d=a;//记录最大公约数
        return;
    }
    gcd(b,a%b,y,x);//往下递归,求出x,y
    y-=(a/b)*x;
}
int main()
{
    int x,y;
    scanf("%d%d%d",&a,&b,&c);
    gcd(a,b,x,y);
    cout<<<"x:"<x*(c/d)<<" y:"<<y*(c/d);
    return 0;
}


回到这题

这题怎么用扩展欧几里得呢? 同余方程ax≡b(mod c)如果有解,则存在整数k,使得b=ax-kc,和上面ax+by=c一样的道理,可以知道gcd(a,c)|b。而这里ax ≡ 1 (mod b),所以可以知道gcd(a,b)|1,所以a,c互质。

然后。。。

(a·x)%b=1%b -> (a·x-1)%b=0 -> a·x=k·b+1 (k∈Z) -> a·x-k·b=1 -> a·x-k·b=gcd(a,b)

于是扩展欧几里得就来了。。。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a,b;
void gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }
    gcd(b,a%b,y,x);
    y-=(a/b)*x;
}
int main()
{
    int x,y;
    scanf("%d%d",&a,&b);
    gcd(a,b,x,y);
    cout<<(x+b)%b;
    return 0;
}