Editorial for İlke the Agile
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000000
#define MOD 998244353
long long fact[MAXN];
long long inv[MAXN];
long long finv[MAXN];
long long C(int a, int b)
{
if (a < b || b < 0)
return 0;
return fact[a] * finv[b] % MOD * finv[a - b] % MOD;
}
long long gcd(long long n, long long m)
{
while (n != 0)
{
long long temp = n;
n = m % n;
m = temp;
}
return m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, a, b;
cin >> k >> a >> b;
int slimDown = gcd(a, b);
a /= slimDown, b /= slimDown;
fact[0] = finv[0] = inv[1] = 1;
for (int i = 2; i < MAXN; i++)
inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
for (int i = 1; i < MAXN; i++)
{
fact[i] = fact[i - 1] * i % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
int result = 0;
for (int length = 1; length * b < k; length++)
result = (result + C(length * b, length * a)) % MOD;
result = result * 2 % MOD;
cout << result << '\n';
return 0;
}