[ZLXOI2015]殉国数论扩展欧几里得

题目大意：已知a,b,c，求满足ax+by=c （x>=0,y>=0）的（x+y）最大值与最小值与解的个数。

直接exgcd，求出x，y分别为最小正整数的解，然后一算就出来啦

#include<cstdio>

#include<iostream>

#define ll long long

using namespace std;

ll a,b,c,x,y,d,bd,ad,X1,Y1,X2,Y2;

ll Abs(ll x){

	return x>=0?x:-x;

}

ll exgcd(ll a,ll b,ll &x,ll &y){

	if(b==0){

		x=1; y=0;

		return a;

	}

	int gcd=exgcd(b,a%b,x,y);

	int t=x;

	x=y;

	y=t-(a/b)*x;

	return gcd;

}

int main()

{

	//freopen("BlackHawk.in","r",stdin);

	//freopen("BlackHawk.out","w",stdout);

	scanf("%lld%lld%lld",&a,&b,&c);

	d=exgcd(a,b,x,y);

	//printf("%lld\n",d);

	if(c%d!=0){

       printf("-1 -1\n0\n");

       return 0;

	}

	x*=c/d; y*=c/d;

	//printf("%lld  %lld\n",x,y);

	bd=b/d; ad=a/d;

	X1=(x%bd+bd)%bd;

	ll t=(X1-x)/bd;

	Y1=y-t*ad;

	ll num1=X1+Y1;

	//printf("%lld  %lld\n",X1,Y1);

	if(Y1<0){

       printf("-1 -1\n0\n");

       return 0;

	}

	Y2=(y%ad+ad)%ad;

	t=(Y2-y)/ad;

	X2=x-t*bd;

	ll num2=X2+Y2;

	//printf("%lld  %lld\n",X2,Y2);

	if(X2<0){

       printf("-1 -1\n0\n");

       return 0;

	}

	if(num2<num1){t=num1; num1=num2; num2=t;}

	printf("%lld %lld\n",num1,num2);

	t=Abs((X1-X2)/bd)+1;

	printf("%lld\n",t);

}

巴特西

[ZLXOI2015]殉国数论扩展欧几里得

最新文章

热门文章

巴特西

[ZLXOI2015]殉国 数论 扩展欧几里得

最新文章

热门文章

[ZLXOI2015]殉国数论扩展欧几里得