洛谷P6060 [加油武汉]传染病研究

一道不错的数学题

Solution

看到约数个数就想到枚举约数，但对于每个询问都枚举显然不现实，但是我们可以将大致的方向锁定在这方面，是否可以预处理出一定的东西，然后低复杂度询问呢？

我们想到预处理出和n有关的一些东西，那么答案就变成和k有关的式子了。

联想到约数个数函数的性质

\[\sigma_0 (n)=\prod (1+\alpha_i)
\]

那么答案显然为

\[\sum_{i=1}^n \prod_j (1 + k\alpha_j)
\]

这个东西在预处理出\(\alpha_i\)后是一个关于\(k\)的多项式

仔细看一下，发现这个式子一个美妙的地方在于\(\alpha_i\)和具体是哪个质因子无关，如此美妙！！

于是我们直接使用线性筛把这个多项式的系数处理出来就行了！！

Code

#include <cstdio>

#include <iostream>

#define LL long long

using namespace std;

inline int read() {

	int res = 0, flag = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = 1;

	for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);

	if(flag) res = ~res + 1;

	return res;

}

const int N = 1e7, L = 8;

const LL P = 998244353;

bool vis[N + 10];

int a[N + 10][9], p[1000000], tot;

int n, T;

LL pw[20], k, ans;

void Sieve() {

	a[1][0] = 1;

	for(register int i = 2; i <= N; ++i) {

		if(!vis[i]) p[++tot] = i, a[i][0] = 1, a[i][1] = 1;

		for(register int j = 1, v; j <= tot; ++j) {

			v = i * p[j]; if(v > N) break;

			vis[v] = 1;

			if(!(i % p[j])) {

				int q = v, cnt = 0;

				while(!(q % p[j])) q /= p[j], ++cnt; a[v][0] = 1;

				for(int k = 0; k < L; ++k) a[v][k + 1] = (a[q][k] * cnt + a[q][k + 1]) % P;

				break;

			}

			a[v][0] = 1;

			for(int k = 0; k < L; ++k) a[v][k + 1] = a[i][k] + a[i][k + 1];

			for(int k = 0; k <= L; ++k) a[v][k] %= P;

		}

	}

	for(int i = 1; i <= N; ++i) for(int j = 0; j <= L; ++j) (a[i][j] += a[i - 1][j]) %= P;

	return ;

}

int main() {

	Sieve(), pw[0] = 1;

	T = read();

	while(T --) {

		n = read(), k = read(), ans = 0;

		for(int i = 1; i <= L; ++i) pw[i] = pw[i - 1] * k % P;

		for(int i = 0; i <= L; ++i) (ans += pw[i] * (LL)a[n][i]) %= P;

		printf("%d\n",ans);

	}

}

洛谷P6060 [加油武汉]传染病研究的相关教程结束。