洛谷 P6060 - [加油武汉]传染病研究（数论）

一道不算太难的题，题解稍微写写吧（

首先根据约数个数和公式，对于一个 \(n=p_1^{\alpha_1}·p_2^{\alpha_2}·\cdots·p_m^{\alpha_m}\)，显然有 \(D(n^k)=\prod\limits_{i=1}^m(k\alpha_i+1)\)，由于每次询问给定的 \(k\) 不固定，我们无法一次性直接对所有 \(k\) 都算一波答案。不过注意到对于一个 \(n\in[1,10^7]\) 而言，其质因子个数不会超过 \(8\)，这也就启发我们，上面的 \(\prod\) 展开后肯定是关于 \(k\) 的次数不超过 \(8\) 的多项式，因此考虑对每个 \(n\) 求出其对应的多项式的系数然后累加求个前缀和，这样我们即可在 \(\mathcal O(8)\) 的复杂度内回答询问。那么怎么对每个 \(n\) 求出其对应的多项式呢？考虑一个非常 naive 的 DP，首先我们对于每个数求出其最小质因子 \(mnp_i\)——这显然可以一遍线性筛搞定，学过一丁点数论的人都能够搞定。我们再找出 \(mnp_i\) 在 \(i\) 中的次数，假设为 \(\alpha\)，那么我们记 \(x=\dfrac{i}{mnp_i^{\alpha}}\)，那么显然就有 \(f_{i,j}=f_{x,j-1}·\alpha+f_{x,j}\)，其中 \(f_{i,j}\) 为 \(i\) 对应的多项式第 \(j\) 项的系数，随便递推一下即可。

时间复杂度 \(\mathcal O(8·n)\)。这个故事告诉我们下次看到数论题目，有时候也可以从每个数不同质因子个数很小这一点出发，可以获得不错的复杂度。

const int MAXN=1e7;

const int OMEGA=8;

const int MOD=998244353;

int pr[MAXN/10+5],prcnt=0,mnp[MAXN+5],omega[MAXN+5];

bitset<MAXN+5> vis;

int s[MAXN+5][OMEGA+2];

void sieve(int n){

	for(int i=2;i<=n;i++){

		if(!vis[i]) mnp[i]=i,pr[++prcnt]=i,omega[i]=1;

		for(int j=1;j<=prcnt&&pr[j]*i<=n;j++){

			vis[i*pr[j]]=1;mnp[i*pr[j]]=pr[j];

			if(i%pr[j]==0){omega[i*pr[j]]=omega[i];break;}

			omega[i*pr[j]]=omega[i]+1;

		}

	} s[1][0]=1;

	for(int i=2;i<=n;i++){

		int tmp=i,sum=0,p=mnp[i];

		while(tmp%p==0) tmp/=p,sum++;

		for(int j=0;j<=omega[i];j++) s[i][j]=s[tmp][j];

		for(int j=0;j<omega[i];j++) s[i][j+1]+=s[tmp][j]*sum;

	}

	for(int i=0;i<=OMEGA;i++) for(int j=1;j<=n;j++)

		s[j][i]=(s[j-1][i]+s[j][i])%MOD;

}

int pw[OMEGA+2];

int main(){

	sieve(MAXN);int qu;scanf("%d",&qu);

	while(qu--){

		int n,k,res=0;scanf("%d%d",&n,&k);

		for(int i=(pw[0]=1);i<=OMEGA;i++) pw[i]=1ll*pw[i-1]*k%MOD;

		for(int i=0;i<=OMEGA;i++) res=(res+1ll*pw[i]*s[n][i])%MOD;

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

	}

	return 0;

}

巴特西

洛谷 P6060 - [加油武汉]传染病研究（数论）

最新文章

热门文章