24暑假集训day3下午

实现代码：

int exgcd(int a,int b, int &x, int &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int d = exgcd(b, a % b, x, y);
	int k = x;
	x = y;
	y = k - (a / b) * y;
	return d;
}
int main(){
	int a = read(), b = read();
	int x, y;
	int d = exgcd(a, b, x, y);
	cout << d << " " << x << " " << y << '\n';
	return 0;
}

#define ll long long 
ll fac[N], ifac[N];
const ll p=998244353;
ll power(ll a, ll b){
	ll ret = 1;
	while (b){
		if(b & 1){
			ret = ret * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return ret;
}
ll c(int a, int b){
	if(a < b || b < 0){
		return 0;
	}
	return fac[a] * ifac[b] % p * ifac[a - b]% p;
}
void initialize(){
	fac[0]= 1;
	for(int i=1; i < N; i++){
		fac[i] = fac[i - 1] * i % p;
	}
	ifac[N - 1] = power(fac[N - 1], p - 2);
	for(int i = N - 2;i >= 0;i--){
		ifac[i]= ifac[i + 1] * (i + 1) % p;
	}
}

小凯的数字

思路:

我们知道 \(