传送门

要求求积性函数 f(x) 的前缀和，f(prim) 是一个关于prim的简单多项式，f(prim^k) 可以快速计算

求法：

Min25 筛分为两部分，第一部分处理素数的幂在  的前缀和

即     

Min25 的核心思想就是考虑小于根号n的质数可以出去大于根号n的合数的贡献

因此我们可以利用这个性质避免计算大于根号n的数的幂

设  为已经筛了 j 个倍数，<= i 的数的 k 次幂和

 为前 i 个质数的 k 次幂和， 

换句话说，f 的作用就是一个质数一个质数去脱合数的衣服，当考虑完小于根号n的质数后，所有合数也被扒完了

考虑多加一个质数会多拔去多少合数的贡献，这些贡献就是

但这样会把质数的贡献减去，所以我们要加上质数的贡献

这样以来我们已经可以处理一些问题了，比如说 <=n的质数个数（0次幂），质数和 （1次幂）

第二部分就是把合数的贡献用积性函数的性质加回去

 表示 2 -- i 所有 Min(x) >= prim(j) 的和

递推分为两部分考虑，一是大于等于pi 的质数，一是合数

质数的贡献我们已经知道，现在考虑如何加上合数的贡献，自己枚举合数的最小质因子与次数

于是有   

后面一坨是因为没有考虑一个质数的次方的贡献

 

一些细节：

我们发现求 f 的时候，n 只需要用到所有  的状态，而  

于是我们可以直接整除分块预处理 n / i 的所有状态然后离散化

//Part 1
for(ll l = 1, r; l <= n; l = r + 1){
    ll v = n / l; r = n / v; 
	if(v <= S) id1[v] = ++m; else id2[n / v] = ++m;
	w[m] = v; ll x = v % Mod;
	f1[m] = (x * (x+1) / 2) % Mod - 1; 
	f2[m] = mul(mul(x, x+1), mul(mul(2, x)+1, inv6)) - 1;
}
for(int i = 1; i <= tot; i++){
	for(int j = 1; j <= m && prim[i] * prim[i] <= w[j]; j++){
		ll k = Id(w[j] / prim[i]);
		f1[j] = dec(f1[j], mul(prim[i], dec(f1[k], s1[i-1])));
		f2[j] = dec(f2[j], mul(mul(prim[i], prim[i]), dec(f2[k], s2[i-1])));
	}
} 

// Part 2
ll Solve(ll x, int p){
	ll k = Id(x), ans = dec(dec(f2[k], f1[k]), dec(s2[p-1], s1[p-1]));
	for(int i = p; i <= tot; i++){
		if(prim[i] * prim[i] > x) break;
		for(ll e = 1, l = prim[i]; l <= x; l *= prim[i], e++){
			ll v = l % Mod;
			if(l * prim[i] <= x) ans = add(ans, mul(f(v), Solve(x / l, i + 1)));
			if(e > 1) ans = add(ans, f(v));
		}
	} return ans;
}