Рассмотрим произвольный хороший массив, поделим все его элементы на первый и уберем все повторяющиеся элементы. Получившийся массив назовём задающим, а все его префиксы недозадающими. $$$\newline$$$ Из задачи о шарах и перегородках, для задающего массива длины $$$m$$$ с последним элементом $$$x$$$, число хороших массивов, для которых он является задающим = $$$\lfloor \frac{c}{x} \rfloor * {n - 1 \choose m - 1}$$$ $$$\newline$$$ Тогда наивное решение — перебор всех задающих массивов $$$\newline$$$ Несложно понять, что для массива $$$a$$$ число хороших, для которых он будет недозадающим зависит только от его длины и последнего элемента, а именно $$$f(m, x) = \lfloor \frac{c}{x} \rfloor * {n - 1 \choose m - 1} + \sum\limits_{t = 2}^{\lfloor \frac{c}{x} \rfloor}f(m + 1, tx)$$$, где $$$f(m, x)$$$ — число хороших, для которых массив с длиной $$$m$$$ и последним элементом $$$x$$$ будет недозадающим. $$$\newline$$$ В таком случае мы можем оптимизировать перебор используя запомининие ответов, однако на время возникают проблемы с памятью $$$\newline$$$ Из формулы $$$f$$$ можно сказать, что $$$\forall x_1, x_2, \lfloor \frac{c}{x_1} \rfloor = \lfloor \frac{c}{x_2} \rfloor: f(m, x_1) = f(m, x_2)$$$. Тогда при подсчёте $$$f$$$ мы можем не просто перебирать все значения $$$t$$$, а объединять $$$t$$$ с одинаковыми значениями $$$\lfloor \frac{c}{xt} \rfloor$$$ $$$\newline$$$ Также это значит, что при запоминании ответов мы можем не все ответы сохранять в $$$f(m, x)$$$, а только те, в которых $$$x \leq \sqrt{c}$$$, а остальные сохранять в $$$g(m, \lfloor \frac{c}{x} \rfloor)$$$ $$$\newline$$$ P. S. Сложно посчитать ассимптотику решения, однако оно работает очень быстро: на тесте $$$n = c = 5 * 10^7$$$, оно работает за $$$296$$$ мс., а на тесте $$$n = c = 10^9$$$, оно работает за $$$2792$$$ мс., на больших тестах решение работает значительно дольше из-за нужды замены int на long long

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const ll MOD = 998244353;
const ll LOGC = 31;
const ll SQRTC = 31600;
ll choose[LOGC];

ll pw(ll a, ll m) {
    if (!m)
        return 1;
    a %= MOD;
    if (m % 2)
        return a * pw(a, m - 1) % MOD;
    return pw(a * a, m / 2);
}

int f[LOGC][SQRTC];
int g[LOGC][SQRTC];

int brute_force(int n, int c, int x, int m) {
    int cdivx = c / x;
    if (x < SQRTC && f[m][x]) {
        return f[m][x];
    }
    if (cdivx < SQRTC && g[m][cdivx]) {
        return g[m][cdivx];
    }
    int ans = cdivx * choose[m - 1] % MOD;
    if (m < n) {
        for (int t = 2; t <= cdivx;) {
            int cdivnx = c / (x * t);
            int nx = t * x;

            // aa - наибольшее число такое, что c / nx == (c / (nx + (aa - 1) * x))
            ll aa = 1;
            while ((nx + (2 * aa - 1) * x) * cdivnx <= c) {
                aa *= 2;
            }
            for (ll t = aa; t > 0; t >>= 1) {
                if ((nx + (aa + t - 1) * x) * cdivnx <= c)
                    aa += t;
            }

            ans += aa * brute_force(n, c, nx, m + 1) % MOD;
            t += aa;
            ans %= MOD;
        }
    }
    if (x < SQRTC)
        f[m][x] = ans;
    if (cdivx < SQRTC)
        g[m][cdivx] = ans;
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, c;
    cin >> n >> c;
    choose[0] = 1;
    for (int i = 1; i < LOGC; ++i) {
        choose[i] = choose[i - 1] * (n - i) % MOD * pw(i, MOD - 2) % MOD;
    }
    cout << brute_force(n, c, 1, 1) << endl;
}