\(\text{Solution}\)
发现题目就是求 \(\sum[\prod_{i=1}^k x_i \le n]\)
\(k \le 10^9\) 太可怕了
然而发现如果限定 \(x_i > 1\) 那么 \(i \le \log n\)
于是我们可以愉快地统计了
设 \(f_i(n)\) 表示将 \(n\) 分成 \(i\) 份使 \(x_i > 1\) 的方案数
那么 \(f_i(n)=\sum_{d|n}f_{i-1}(\frac n d)-f_{i-1}(n)\)
那个减号就是减去 \(d=1\) 时的情况
先不考虑减法,发现它的转移就是 \(Dirichlet\) 前缀和
于是处理 \(f\) 可做到 \(O(n \log n \log\log n)\)
每个询问还要枚举多少个位置不填 \(1\),组合算一下方案
总的就是 \(O(n \log n \log\log n + Q \log n)\)
\(\text{Code}\)
#include <cstdio>
#include <iostream>
#define re register
#define LL long long
using namespace std;
const int N = 5e5 + 5, P = 998244353;
int mxR, mxK, q, log[N], tot, pr[N], vis[N];
LL f[20][N], inv[20];
inline void read(int &x)
{
x = 0; int f = 1; char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : f), ch = getchar();
while (isdigit(ch)) x = (x<<3) + (x<<1) + (ch^48), ch = getchar();
x *= f;
}
void sieve(int n)
{
for(re int i = 2; i <= n; i++)
{
if (!vis[i]) pr[++tot] = i;
for(re int j = 1; j <= tot && pr[j] * i <= n; j++)
{
vis[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
}
LL Add(LL x, LL y)
{
x += y;
if (x > P) x -= P;
return x;
}
int main()
{
freopen("easy.in", "r", stdin), freopen("easy.out", "w", stdout);
read(mxR), read(mxK), read(q);
sieve(mxR);
for(re int i = 2; i <= mxR; i++) log[i] = log[i >> 1] + 1, f[1][i] = 1;
int lg = log[mxR];
for(re int i = 2; i <= lg; i++)
{
for(re int j = 1; j <= mxR; j++) f[i][j] = f[i - 1][j];
for(re int j = 1; j <= tot; j++)
for(re int k = 1; k * pr[j] <= mxR; k++)
f[i][k * pr[j]] = Add(f[i][k * pr[j]], f[i][k]);
for(re int j = 1; j <= mxR; j++) f[i][j] = Add(f[i][j], P - f[i - 1][j]);
}
for(re int i = 1; i <= lg; i++)
for(re int j = 1; j <= mxR; j++) f[i][j] = Add(f[i][j], f[i][j - 1]);
inv[1] = 1;
for(re int i = 2; i <= lg; i++) inv[i] = (P - P / i) * inv[P % i] % P;
for(int l, r, k; q; q--)
{
read(l), read(r), read(k);
LL ans = 0, c = 1;
for(re int i = 1; i <= log[r]; i++)
{
c = c * (k - i + 1) % P * inv[i] % P;
ans = Add(ans, (f[i][r] - f[i][l - 1] + P) * c % P);
}
printf("%lld\n", ans + (l <= 1));
}
}