sieve dp#

我们定义 $g(n, j)$ 为$\sum_{i=2}^{n} [i \in Prim \, or \, minprims(i) > P_j] F(i)$

人话就是 $i$ 要么是质数， 要么最小质因子大于第$j$个质数

意思就是 质数和还没被前$j$个数筛掉的 $F(x)$ 的和

当前状态是$g(n, j)$

考虑转移 就像是模拟埃氏筛

1. 如果$j$ 不是质数 $g(n, j) = g(n, j - 1)$

2. 如果$j$ 是质数

   • ​ 如果$j^2 > n$ 则 $g(n, j) = g(n, j - 1)$, 因为它能筛掉的数至少是 $j ^ 2$

   • 否则 它可以筛掉的数可以写成 $j \times m$ 其中m的最小质因子要大于等于$j$

     ​ 即$minprims(m) \ge j$

     ​ 所以

     $$g(n, j) = j \times (g(\lfloor \frac{n}{j}\rfloor, j - 1) - g(j -1, j -1))$$

     ​ $g(\lfloor \frac{n}{j}\rfloor, j - 1)$表示 $m$ 中没被筛掉的数的和 就是$j -1$ 中的质数和最小质因子要大于等于$j$

     ​ 所以减掉$g(j -1, j -1)$ 然后乘上$j$ 就是答案

在第二个转移转移过程中 有个 乘 $j$ 这是因为我们本来计算的就是质数的和， 非质数不在我们的计算范围之内我们应该筛掉它，筛掉它，那么它的值应该质因子值的乘积才对

常见 就是 f(i) = i, f(i) = 1等

来分析下复杂度 首先只要$\sqrt n$ 以内的质数就可以把 它全部筛完， 因为大于$\sqrt n$的质数最多只有一个，而它不会筛掉任何数 所以$1 \le j \le \sqrt n$ 又因为$\lfloor \frac{n}{j}\rfloor$ 且 $\lfloor \frac{\lfloor \frac{n}{a}\rfloor}{b} \rfloor = \lfloor \frac{n}{ab} \rfloor$ 所以至多只有$\sqrt n$ 个数， 只有 $j ^2 \le n$ 才会发生转移

所以$\frac{n^\frac{3}{4}}{logn}$ 的复杂度

样例代码，其中$h$ 函数是 $f(x) = 1$ , $g$ 函数是$f(x) = i$

constexpr int mod = 1e9 + 7, maxn = 1e5 + 5;
using mint = ModInt<mod>;
vector<int>prim;
vector<mint>sump(1);
vector<int>vis(maxn);
void init(int n){
	vis[1] = 1;
	for(int i = 2; i <= n; i++){
		if(!vis[i]){
			prim.push_back(i);
			sump.push_back(sump.back() + i);
		}
		for(int j = 0; prim[j] * i <= n; j++){
			vis[i * prim[j]] = 1;
			if(i % prim[j] == 0)break;
		}
	}
}
void solve(){
    int n; cin >> n;
    int B = sqrt(n);
    init(B);
    vector<int>id1(B + 1), id2(B + 1);
    vector<int>w(2 * B + 1);
    vector<mint>g(2 * B + 1), h(2 * B + 1);
    int tot = 0;
    for(int i = 1, j; i <= n; i = j + 1){
    	j = n / (n / i);
    	w[++tot] = n / i;
    	h[tot] = mint(w[tot] - 1);
    	g[tot] = mint(w[tot]) * (w[tot] + 1) * mint(2).inv() - 1;
    	if(w[tot] <= B)id1[w[tot]] = tot;
    	else id2[j] = tot;
    }
    int sz = prim.size();
    for(int i = 0; i < sz; i++){
    	for(int j = 1; j <= tot; j++){
    		if(prim[i] * prim[i] > w[j])break;
    		int k = w[j] / prim[i];
    		if(k <= B) k = id1[k];
    		else k = id2[n / k];
    		h[j] -= h[k] - i;
    		g[j] -= prim[i] * (g[k] - sump[i]);
    	}
    }

第二步 Min25筛#

考虑把上面的dp倒过来加入被筛掉的数

我们定义$s(n, j)$ 表示$2$ ~ $n$ 中 最小质因子大于等于 第$j$ 个质数 的数 和质数的 $F(x)$ 的和

那么最终答案就是 $s(n, 0)$

同样的考虑只有 $j^2 \le n$ 时才发生转移

​ 被$j$ 筛掉的数的形式 长 $j^k \times m$ 其中$m$ 的最小质因子大于 $j$ 注意这里是大于(保证互质)， 上面的是大于等于

​ 那么有

下面介绍一种递归的实现方式

把 $s(n,j)$分为两个部分计算，一部分是所有质数的和，一部分是所有合数的和

我们定义$s(n, j)$ 表示$2$ ~ $n$ 中 最小质因子大于等于 第$j$ 个质数 的数 的 $F(x)$ 的和

那么转移里面的$(s(\lfloor \frac{n}{j^c} \rfloor, j) - F_{prim}(j))$ 可以直接用 $s(\lfloor \frac{n}{j^c} \rfloor, j)$ 替代

auto Min_25 = [&](auto self, int x, int y) -> mint{
    	if(x <= 1)return 0;
    	int k = x;
    	if(k <= B) k = id1[k];
    	else k = id2[n / k];
    	mint ret = g[k] - sump[y] - h[k] + y;//计算质数的贡献
    	if(y == 0)ret += 2;
    	for(int i = y; i < sz; i++){
    		if(prim[i] * prim[i] > x)break;
    		int t1 = prim[i];
    		int t2 = prim[i] * prim[i];
    		for(int e = 1; t2 <= x; e++){
                //计算合数的贡献
    			ret += self(self, x / t1, i + 1) * (prim[i] ^ e) + (prim[i] ^ (e + 1));
    			t1 = t2;
    			t2 *= prim[i];
    		}
    	}
    	return ret;
    };