Cptraser/ 十一月 8, 2018/ 2018.11/ 0 comments

exgcdOI中一类常见问题的做法
对于方程ax+by=c,如果有!(c\% gcd(a,b)),则该方程一定至少有一组解。
以下模板可以求出一组非负或正整数解。

int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void exgcd(int &x,int &y,int a,int b){
    if(!b)return (void)(x=1,y=0);
    return (void)(exgcd(y,x,b,a%b),y-=a/b*x);
}

int calc(int a,int b,int c){
    p=gcd(a,b);
    if(c%p)return -1;//无解
    exgcd(x,y,a,b);
    x=x*c/p;//还原方程(gcd->c)
    k=abs(b/p);//还原后b约去gcd
    x=(x%k+k)%k;//非负解
    if(!x)x+=k;//正整数解
    y=(c-a*x)/b;//判断y是否可行
    while(y<0)x+=k,y=(c-a*x)/b;
    return x;
}

BZOJ1477青蛙的约会
求解方程:am+x=an+y+bL
化简:a(n - m)+bL=x - y,exgcd即可。

#include <cstdio>
#include <algorithm>
using namespace std;

long long x,y,n,m,a,k,L,p,g;
long long gcd(long long x,long long y){return !y?x:gcd(y,x%y);}
void exgcd(long long &x,long long &y,long long a,long long b){
    if(!b)return (void)(x=1,y=0);
    return (void)(exgcd(y,x,b,a%b),y-=a/b*x);
}


int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
    if(n<m)swap(n,m),swap(x,y);
    if((x-y)%gcd(n-m,L))return puts("Impossible"),0;
    p=gcd(n-m,L),exgcd(a,k,n-m,L),L/=p;
    printf("%lld\n",(a*(x-y)/p%L+L)%L),0;
}

CF787A TheMonster
求解方程:ax+b=cy+d
化简:ax-cy=d-b,exgcd即可。

#include <cstdio>
#include <algorithm>
using namespace std;

int a,b,c,d,p,x,y,Mod,k;
int abs(int x){return x<0?-x:x;}
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void exgcd(int &x,int &y,int a,int b){
    if(!b)return (void)(x=1,y=0);
    return (void)(exgcd(y,x,b,a%b),y-=a/b*x);
}

int calc(int a,int b,int c){
    exgcd(x,y,a,b);
    x=x*c/p,k=abs(b/p);
    x=(x%k+k)%k;
    y=(c-a*x)/b;
    while(y<0)x+=k,y=(c-a*x)/b;
    return x;
}


int main()
{
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if(d<b)swap(a,c),swap(b,d);
    if((d-b)%(p=gcd(a,-c)))return puts("-1"),0;
    printf("%d",calc(a,-c,d-b)*a+b);
}

CF7C Line
方程:ax+by=-c
需要判断bk0的情况。

#include <cstdio>
#include <algorithm>
using namespace std;

long long a,b,c,p,x,y,k;
long long gcd(long long x,long long y){return !y?x:gcd(y,x%y);}
void exgcd(long long &x,long long &y,long long a,long long b){
    if(!b)return (void)(x=1,y=0);
    return (void)(exgcd(y,x,b,a%b),y-=a/b*x);
}

void calc(long long a,long long b,long long c){
    exgcd(x,y,a,b);
    x=x*c/p,k=abs(b/p);
    if(k)x=(x%k+k)%k;else x=0;
    if(b)y=(c-a*x)/b;else y=0;
}


int main()
{
    scanf("%lld%lld%lld",&a,&b,&c);
    if((-c)%(p=gcd(a,b)))return puts("-1"),0;
    calc(a,b,-c),printf("%lld %lld",x,y);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*