\(\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));

	}

}

巴特西

NOIP 模拟赛简单题

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章

巴特西

NOIP 模拟赛 简单题

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章

NOIP 模拟赛简单题