用杜教篩求解數論函數前綴和

• 2020 年 4 月 25 日
• 筆記
• 數學——杜教篩

杜教篩用來求數論函數\(f\)前綴和。複雜度為\(O(n^{\frac{2}{3}})\)

前提

如果我們要求\(S(n)=\sum\limits_{i=1}^nf(i)\)，那麼需要找到一個數論函數\(g\)，滿足\(g\)的前綴和可以非常快速的求出來，並且\(g*f\)的前綴和可以非常快速的求出來。

推導

既然\(g*f\)的前綴和可以非常快速的求出來，我們就求\(g*f\)的前綴和。

即\(\sum\limits_{i=1}^n\sum\limits_{d|i}g(\frac{i}{d})f(d)\)。

然後我們想得到的是\(\sum\limits_{i=1}^nf(i)\)。所以我們讓上面的式子減去一個\(\sum\limits_{i=1}^n\sum\limits_{d|i,d\neq i}g(\frac{i}{d})f(d)\)。

對於後面這個式子,我們用\(\frac{n}{d}\)來代替\(d\)，就變成了

因為\(g\)的前綴和可以快速求出，所以直接數論分塊，後面的\(S(\frac{n}{d})\)直接遞歸就好了。

這樣我們得到的是\(\sum\limits_{i=1}^ng(1)f(i)=g(1)\sum\limits_{i=1}^n f(i)\)，所以答案除以\(g(1)\)（一般為1）就好了。

例子

以求\(\varphi\)的前綴和為例。因為\(f*1=Id\)，\(1\)和\(Id\)的前綴和都非常好求，所以我們令\(g\)為\(1\)即可。

再來推一下\(\mu\)的前綴和。因為\(\mu * 1= \epsilon\)，\(1\)和\(\epsilon\)的前綴和都非常好求，所以還是令\(g=1\)

關於預處理

這樣直接搜的複雜度是\(O(n^{\frac{3}{4}})\)，為了使複雜度更優，我們需要先預處理出一部分答案，如果我們預處理除了\([1,K]\)的答案，當計算\([1,K]\)中的結果時，直接返回即可。

可以證明當\(K\)取\(n^{\frac{2}{3}}\)時，複雜度最優秀為\(n^{\frac{2}{3}}\)

關於記憶化

為了讓複雜度是正確的，我們肯定要將每次算出的結果記憶化下來。因為\(n\)比較大，所以需要用\(map\)來記憶化。這樣複雜度就會多個\(log\)

還有一種方法，因為我們每次遞歸到的\(x\)肯定滿足:所有滿足\(\frac{n}{y}=\frac{n}{x}\)的\(y\)中，只有\(x\)會被計算到。所以我們可以用一個數組ma記憶化，當查詢的\(n\)小於等於\(K\)時，我們直接範圍答案，當查詢的\(n\)大於\(K\)時，我們查看\(ma[\lfloor \frac{n}{K}\rfloor]\)中的值即可。

當有多次詢問時，第二種方法需要清空，複雜度可能不如第一種。

代碼

以求\(\varphi\)的前綴和為例。

void pre() {
	phi[1] = 1;
	for(int i = 2;i < N;++i) {
		if(!vis[i]) {
			prime[++tot] = i;
			phi[i] = i - 1;
		}
		for(int j = 1;j <= tot && prime[j] * i < N;++j) {
			vis[prime[j] * i] = 1;
			if(i % prime[j]) {
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			}
			else {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
	for(int i = 2;i < N;++i) phi[i] = (phi[i] + phi[i - 1]) % mod;
}
ll MAX;

ll PHI(ll n) {
	if(n < N) return phi[n];
	
	if(vis[MAX / n]) return maphi[MAX / n];
	vis[MAX / n] = 1;
	ll ret = (n % mod) * ((n + 1) % mod) % mod * inv % mod;

	for(ll l = 2,r;l <= n;l = r + 1) {
		r = n / (n / l);
		ret -= ((r - l + 1) % mod) * PHI(n / l) % mod;
		ret %= mod;
	}
	return maphi[MAX / n] = ret;
}