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.
#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;
}