【数组题解】
关键词： 线性筛、最小质因数
本题主要考察对于欧拉筛和最小质因数的理解和应用。
题目大意：给定长度 n 和最大值 c，求长度为 n 的好数组中所有元素不超过 c 的方案数（对 998244353 取模）
定义一个数组 a=[a_1,a_2,…,a_n] 称为 “好数组”，当且仅当对于所有 1≤i <= n - 1，都有：
a_i \% a_{i+1}=0 且 a_i <= c
即：每个元素都能被它后一个元素整除。
首先来看什么是取模。对一个数 y 进行质因数分解 y=p_1^{a_1} *p_2^{a_2}*p_3^{a_3}.....{p_n}^{a_n} 其中 p_i 表示质因数， a_i 表示质因数的个数， n 为不同质因数个数的。
那么如果一个数 x 是另一个数 y 的因数，就是满足它所有质因数的个数都小于等于 y 质因数的个数，并且不能出现 y 没有的质因数。就是满足
x=p_1^{b_1} *p_2^{b_2}*p_3^{b_3}.....{p_n}^{b_n} 其中 对于任意 i 都要有 b_i<=a_i
我们想要算对于不同的开头的好数组的方案数量。对于每一个不同开头 x 计算他的所有的好数组方案数，这个问题等价于，将他的所有质因数分配到 n -1 个位置上。可以不分配完的方案数。
我们对每个质因数分别考虑这个事情，然后最后乘起来。对于每个质因数分别考虑这个事情就是求有非负整数解的方案数：
a_1+a_2+⋯+a_n=x,a_i≥0
不分配完就给他多加一个格子表示浪费了几个就好了。
然后讲一下这样做是为什么。我们对每个位置求后缀和就是这个位置的真实值。而这个方案数可以通过隔板法来得到为 \binom{n+x-1}{x}。总所周知一个数的质因数个数不超过 32。所以这个随便解决。
然后我们就有一个 \mathcal{O}(c*logc) 的提前筛出质数然后对每一个取值质因数分解的解法。但显然这个复杂度是过不了的。
所以我们考虑在线性筛的时候进行这个过程。
for(int i=2;i<=x;i++){
if(!prime_st[i]) prime_p[UP++]=i;
for(int j=0;prime_p[j]<=x/i;j++){
prime_st[prime_p[j]*i]=true;
if(i%prime_p[j]==0) break;
}
}
对于在线性筛中每个数 prime\_p[j]*i 其中 prime\_p[j] 是它的最小质因数。
我们定义 dp[i] 表示每个数的贡献（它所有质因数贡献的和），我们通过对线性筛的观察不难发现，每次相当于对 prime\_p[j]*i 多加了 prime\_p[j] 的贡献。这里分成两种情况，一个是 i 中含有 prime\_p[j] 我们需要算出 有多少个新加进来的质数，然后乘以去掉新加进来的质数的贡献。
if(i%prime_p[j]==0){
int js = 1; // 一开始就有一个prime_p[j]
while(i % prime_p[j] == 0){
i /= prime_p[j];
js ++;
}
// 方案数 = 单个质数个数为js贡献 * i的方案数
}
还有一种相当 i 中没有新加的质数，直接乘一个数贡献就行。
因为对于每个合数 prime\_p[j]*i，只在它的最小质因数筛到它时才被处理一次，并统计该最小质因数的幂次。由于线性筛性质，每个合数最多被处理一次，因此所有合数的处理总时间为 \mathcal{O}(c)，均摊每个数为 \mathcal{O}(1)。而不是看起来的 \mathcal{O}(c*logc)
最后把所有方案加起来就好了。