欧几里得及拓展欧几里得

博主链接

欧几里得

int gcd(int a,int b){

    return (b==0)?a:gcd(b,a%b);    //一条语句搞定（三元运算符）装逼，跟上面略有不同，上面做到t=0,这里做到b=0

}

拓展欧几里得

int gcd(int a,int b){

    return (b==0)?a:gcd(b,a%b);    //一条语句搞定（三元运算符）装逼，跟上面略有不同，上面做到t=0,这里做到b=0

}

ll lcm(ll a, ll b) {
    return a / gcd(a,b) * b;
}
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

拓展欧几里得求整数解个数

ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

ll extend_gcd(ll a, ll b, ll&x, ll&y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll xt = 0, yt = 0;
	ll d = extend_gcd(b, a % b, xt, yt);
	x = yt;
	y = xt - yt * (a / b);
	return d;
}

ll cal(ll a, ll b, ll n) {    //计算ax+by == n的非负整数解组数
	ll x = 0, y = 0, d;
	d = extend_gcd(a, b, x, y);
	if (n % d != 0) {
		return 0;
	}
	x *= n / d, y *= n / d;
	ll LCM = lcm(a, b);
	ll t1 = LCM / a, t2 = LCM / b;
	if (x < 1) {
		ll num = (1 - x) / t1;
		x += num * t1;
		y -= num * t2;
		if (x < 1) {
			y -= t2;
			x += t1;
		}
	}
	if (y < 1) {
		ll num = (1 - y) / t2;
		y += num * t2;
		x -= num * t1;
		if (y < 1) {
			y += t2;
			x -= t1;
		}
	}
	ll ans = x > 0 && y > 0;
	if (ans) {
		ans += min((x - 1) / t1, ((n - 1) / b - y) / t2);
		ans += min((y - 1) / t2, ((n - 1) / a - x) / t1);
	}
	return ans;
}