簡介

Min_25篩據說可以在\(O(\frac{n^{\frac{3}{4}}}{logn})\)處理出含有以下性質的函式f的前綴和:
1.\(f(ab)=f(a)f(b)\)，即f是一個積性函式
2.\(f(p^k)\)可以快速計算，

PS:本文沒有關于復雜度的證明，，，

預處理

首先要預處理兩個東西，一個是\(\sqrt{n}\)(n為詢問的值域)內的質數，直接線性篩就好了，用\(pri[i]\)表示第i個質數，設共有\(m\)個質數

另一個是\(g(n,j)\)，表示所有\(x\in[1,n]\)中滿足x最小質因子大于\(pri[j]\)或者x是質數的\(f(x)\)之和，

這樣一來，\(g(n,m)\)表示的就是\([1,n]\)中所有質數的f值之和，這個東西后面會用到，

那么來看一下這個\(g\)值該如何求，

顯然，如果\(pri_j^2>n\)那么\(g(n,j)=g(n,j-1)\)，因為這時的\(g(n,j-1)\)已經只表示\([1,n]\)中所有質數的f之和，\(g(n,j)\)并不會比\(g(n,j-1)\)多洗掉掉任何東西，

如果\(pri_j^2\le n\)呢？我們可以理解為埃氏篩法的程序，\(g(n,j)\)與\(g(n,j-1)\)的差別就是篩掉了\(pri_j\)的倍數，那么就好像可以轉移了，問題就在于如何計算出所有\(pri_j\)的倍數所產生的貢獻，前面說到這是一個積性函式，所以我們將這些要洗掉的數全都提出來一個\(pri_j\)，那么剩下的就是\([1,\frac{n}{pri_j}]\)了，因為需要\(pri_j\)是這些數字的最小質因子，所以實際上區間\([1,pri_j-1]\)內的數字是不可以的，所以要洗掉的區間實際上是\([pri_j,\frac{n}{pri_j}]\)所以要洗掉的數字就是\(f(pri_j)[g(\frac{n}{pri_j},j-1)-g(pri_j-1,j-1)]\)，也就是說\(g(n,j)=g(n,j-1)-f(pri_j)[g(\frac{n}{pri_j},j-1)-g(pri_j-1,j-1)]\)

因為最終我們需要的只有\(g(\lfloor\frac{n}{i}\rfloor,m),1\in [1,n]\)，所以空間只需要開一維，每次處理復雜度是\(O(m)\)的（實際上并不到），類似于整除分塊，我們知道\(\frac{n}{i}\)只有\(\sqrt{n}\)級別種取值，復雜度據說是\(O(\frac{n^{\frac{3}{4}}}{logn})\)，

計算答案

上面的東西預處理完了，那么有什么用呢？？

我們再定義一個函式\(S(n,j)\)表示\(x\in[1,n]\)中滿足\(x\)的最小質因子大于等于\(pri_j\)的\(f(x)\)之和，

最終我們要求的答案就是\(S(n,1)+f(1)\)

上面說到，\(g(n,m)(pri_m^2>n)\)可以表示\([1,n]\)中所有質數的\(f\)值之和，

所以我們將\(S(n,j)\)分為質數和合數兩塊來處理，

質數的一塊顯然就是\(g(n,m)-\sum\limits_{k=1}^{j-1}f(pri_k)\)，為什么要減掉后面這一塊？？因為小于\(pri_j\)的質數不包含在\(S(n,j)\)里面呀~

然后考慮合數的一塊該如何求，我們列舉一下這些合數的最小質因子\(k\in[pri_j,pri_m]\)和\(k\)的指數\(e\)，于上方求g的方法類似的，我們可以提出來一個\(pri_k^e\)，那么剩下的就是\([1,\frac{n}{pri_k^e}]\)，他們的f之和就是\(S(\frac{n}{pri_k^e},k)\)，發現這樣無法轉移，那么我們只好從\(S(\frac{n}{pri_k^e},k+1)\)轉移過來，但是這樣\(f(pri_k^{e+1})\)就沒被計算，單獨加上就好了，

綜上所述，

\[S(n,j)=g(n,m)-\sum\limits_{k=1}^{j-1}f(pri_k)+\sum\limits_{k=j}^m\sum\limits_{e=1}^{pri_k^{e+1}\le n}(f(pri_k^{e+1})+f(pri_k^e)S(\frac{n}{pri_k^e},k+1) \]

然后遞回計算即可，這里的復雜度據說也是\(O(\frac{n^{\frac{3}{4}}}{logn})\)，

經典例題

loj6053簡單的函式

定義函式\(f(x)\)滿足以下性質，
1.\(f(1)=1\)
2.\(f(p^c)=p\otimes c\)(p為質數)
3.\(f(ab)=f(a)f(b)（a,b互質）\)

求\(\sum\limits_{i=1}^nf(i)\)，\(n\le 10^{10}\)

思路

發現這些性質恰好吻合了我們一開始要求的性質，
發現除2外所有的質數均為奇數，所以就有\(f(p)=p-1\)（p為奇質數），然后發現這個東西并不是積性函式，沒法預處理g了，怎么辦？
那就把它拆開，拆成\(f_1(p)=p,f_2(p)=1\),那么就有\(f(p)=f_1(p)-f_2(p)\)，然后按照上述方法分別預處理除關于\(f_1\)的\(g(n,m)\)，關于\(f_2\)的\(h(n,m)\)，
要說明的是，我們一開始將所有的合數全都當成奇質數來處理，因為最后都要“篩”掉的，所以沒有影響，

具體細節：

預處理g時，有個式子是\(g(pri_j-1,j-1)\)，也就是前\(j-1\)個質數的前綴和，所以預處理質數時同時預處理一下前綴和，

code

/*
* @Author: wxyww
* @Date:   2019-12-22 17:42:00
* @Last Modified time: 2019-12-24 21:58:42
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 2000010,mod = 1e9 + 7;
ll read() {
	ll x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1; c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = getchar();
	}
	return x * f;
}
int tot;
ll n,m,w[N],pri[N],sum[N],js,vis[N],g[N],h[N];
void pre() {//篩出質數
	for(int i = 2;i <= m;++i) {
		if(!vis[i]) {
			pri[++js] = i;
			sum[js] = sum[js - 1] + i;
			sum[js] %= mod;
		}
		for(int j = 1;j <= js && i * pri[j] <= m;++j) {
			vis[pri[j] * i] = 1;
			if(i % pri[j] == 0) break;
		}
	}
}
int id1[N],id2[N];
ll S(ll now,int x) {
	if(now <= 1 || pri[x] > now) return 0;

	// printf("%lld %d\n",now,x);

	int k;
	if(now <= m) k = id1[now];
	else k = id2[n / now];

	ll ret = (g[k] - h[k] - sum[x - 1] + x - 1) % mod;

	if(x == 1) ret += 2;//f(2)當作1計算，實際上f(2)=3 

	for(int k = x;k <= js && pri[k] * pri[k] <= now;++k) {
		ll p = pri[k];
		for(int e = 1;p * pri[k] <= now;p = p * pri[k],++e) {
			ret += (pri[k] ^ e) * S(now / p,k + 1) % mod + (pri[k] ^ (e + 1));
			ret %= mod;
		}
	}
	return ret;
}

int main() {
	// freopen("1.in","w",stdout);
	n = read();
	m = sqrt(n);
	pre();

	// puts("!!!");
	for(ll l = 1,r;l <= n;l = r + 1) {
		r = n / (n / l);
		ll tmp = n / l;
		w[++tot] = tmp;
		if(tmp <= m) id1[tmp] = tot;//陣列不夠大，通過id1和id2來映射到sqrt(n)以內
		else id2[n / tmp] = tot;

		g[tot] = (tmp + 2) % mod * ((tmp - 1) % mod) % mod;
		
		if(g[tot] & 1) g[tot] += mod;
		
		g[tot] /= 2;
		// g[tot] %= mod;
		h[tot] = tmp - 1;
	}

	// for(int i = 1;i <= tot;++i) printf("%lld ",g[i]);

	for(int j = 1;j <= js;++j) {
		for(int i = 1;i <= tot  && pri[j] * pri[j] <= w[i];++i) {//列舉順序不能顛倒
			ll tmp = w[i] / pri[j];
			int k;
			if(tmp <= m) k = id1[tmp];
			else k = id2[n / tmp];
			g[i] -= pri[j] * (g[k] - sum[j - 1]) % mod;//列舉順序不能顛倒的原因
			g[i] %= mod;
			h[i] -= (h[k] - (j - 1));
			h[i] %= mod;
		}
	}


	// cout<<g[tot - 2]<<endl;

	cout<<(S(n,1) + 1 + mod) % mod;//單獨把1算上 
	return 0;
}

標籤：C++

上一篇：delphi xe 10 無法破解。

下一篇：關于讀取TXT檔案的問題，求大神