• 欢迎光临~

# 杜教筛

[begin{aligned} S(h, n) & = sum_{x=1}^n h(x) \ & = sum_{x = 1}^n sum_{d|x} g(d) f(frac xd) \ & = sum_{d = 1}^n g(d) sum_{x = 1}^{leftlfloor frac n d rightrfloor} f(x) \ & = sum_{d = 1}^n g(d) S(f, leftlfloor frac n d rightrfloor) \ & = g(1) S(f, n) + sum_{d = 2}^n g(d) S(f, leftlfloor frac n d rightrfloor) \ g(1) S(f, n) & = S(h, n) - sum_{d = 2}^n g(d) S(f, leftlfloor frac n d rightrfloor) \ S(f, n) & = frac{1}{g(1)} left( S(h, n) - sum_{d = 2}^n g(d) S(f, leftlfloor frac n d rightrfloor) right) end{aligned}]

[begin{aligned} & sum_{i=1}^{sqrt n} O(sqrt i) + sum_{i=1}^{sqrt n} O(sqrt frac ni) \ = & Oleft(int_{1}^{sqrt n} x^{frac 12} text dxright) + Oleft(int_{1}^{sqrt n} (frac n x)^{frac 12} text dxright) \ = & Oleft(n^{3/4} right) + Oleft(n^{3/4} right) end{aligned}]

[begin{aligned} sum_{i=B}^{sqrt n} O(sqrt frac ni) = Oleft(frac{n}{sqrt B}right) end{aligned}]

(B = n^{2/3}) 得到总时间复杂度 (O(n^{2/3}))

[S(f, n) = frac{1}{g(1)} left( S(h, n) - sum_{d = 2}^n g(d) S(f, leftlfloor frac n d rightrfloor) right) ]

• 欧拉函数 (varphi(n) = sum_{(d,n) =1} 1)
• 莫比乌斯函数 (mu(n))
• 恒等函数 (text I(n) = 1)
• 元函数 (e(n) = [n = 1])
• 单位函数 (text{id} (n) = n)
• 约数个数函数 (text{d} (n) = sum_{d | n} 1)
• 题面里给的函数 (f(n) = small{我怎么知道})

• \$mu * text I = e to f = (f * text I) * mu \$ 该变换即莫比乌斯反演。
• (varphi * text I = text {id} to text{id} * mu = varphi)
• (text{id} * text{id} = text{id} times text d)

## 例题

【模板】杜教筛

(n le 10^{11})

code
``````#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for ( register int (i) = (a); (i) <= (b); ++(i) )
#define pre(i,a,b) for ( register int (i) = (a); (i) >= (b); --(i) )
using namespace std;
const int N = 5e6 + 10, L = 5e6;
int T, n;

int prime[N], cnt, phi[N], mu[N];
inline void sieve() {
phi[1] = mu[1] = 1;
rep(i,2,L) {
if (phi[i] == 0) prime[++cnt] = i, phi[i] = i - 1, mu[i] = - 1;
rep(j,1,cnt) {
int tmp = i * prime[j];
if (tmp > L) break;
if (i % prime[j] == 0) {
phi[tmp] = prime[j] * phi[i]; mu[tmp] = 0;
break;
} else
phi[tmp] = phi[prime[j]] * phi[i]; mu[tmp] = -mu[i];
}
}
rep(i,2,L) phi[i] = phi[i-1] + phi[i], mu[i] = mu[i-1] + mu[i];
}

int _phi[N], _mu[N];
inline int getPhi(int x) {
if (x <= L) return phi[x];
if (~_phi[n / x]) return _phi[n / x];
int ret = 1ll * x * (x + 1) >> 1;
for (int l = 2, r; l <= x; l = r+1) {
r = x / ( x / l );
ret -= (r - l + 1) * getPhi(x / l);
}
return _phi[n / x] = ret;
}

inline int getMu(int x) {
if (x <= L) return mu[x];
if (~_mu[n / x]) return _mu[n / x];
int ret = 1;
for (int l = 2, r; l <= x; l = r + 1) {
r = x / ( x / l );
ret -= (r - l + 1) * getMu(x / l);
}
return _mu[n / x] = ret;
}

signed main() {
sieve(); cin >> T;
while (T--) {
cin >> n;
memset(_phi, -1, sizeof _phi);
memset(_mu, -1, sizeof _mu);
cout << getPhi(n) << ' ' << getMu(n) << 'n';
}
}
``````

[sum^k_{a_1=1}sum^k_{a_2=1}sum^k_{a_3=1}dotssum^k_{a_n=1}gcd(a_1,a_2,a_3,dots,a_n)pmod{ 1000000007} ]

(n,k le 10^{11})

DZY Loves Math IV

[sum_{i=1}^n sum_{j=1}^m varphi(ij) pmod{1000000007} ]

(n le 10^5, m le 10^9)

[S(n, m) = sum_{i=1}^m varphi(in) ]

[begin{aligned} S(n, m) & = sum_{i=1}^m varphi(in) \ & = qsum_{i=1}^m varphi(ip) \ & = qsum_{i=1}^m varphi(frac{p}{gcd(i, p)}) varphi(i) gcd(i, p) \ & = qsum_{i=1}^m varphi(frac{p}{gcd(i, p)}) varphi(i) sum_{d|(i, p)} varphi(d) qquad & (varphi * text{I} = text{id} ) \ & = qsum_{i=1}^m varphi(i) sum_{d|(i, p)} varphileft(frac{dp}{gcd(i, p)} right)qquad & (varphi 是积性的) \ & = qsum_{i=1}^m varphi(i) sum_{d|(i, p)} varphileft(frac{p}{d} right) \ & = qsum_{d|p} varphileft(frac{p}{d} right)sum_{i=1}^{m / d} varphi(id) \ & = qsum_{d|p} varphileft(frac{p}{d} right) S(d, leftlfloorfrac mdrightrfloor) end{aligned}]

Submission。

[sum_{i=1}^n mu(i^2) qquad sum_{i=1}^n varphi(i^2) ]

(n le 10^9)

(mu) 那个显然答案就是 (1)
(varphi)……哦想起来了，放这题是因为想告诉你们 (varphi(n^k) = n^{k-1}varphi(n))。挺好用的。

(f(n) = varphi(n) times n)(f * text{id} = text{id}_2)。剩下的看代码。

Submission。

Lucas的数论

[sum_{i=1}^n sum_{j=1}^n text d(ij) pmod{1000000007} ]

(n le 10^9)

[begin{aligned} &sum_{i=1}^n sum_{j=1}^n text d(ij) \ = & sum_{i=1}^n sum_{j=1}^n sum_{x|i} sum_{y|j} [gcd(x, y) = 1] \ = & sum_{i=1}^n sum_{j=1}^n sum_{x|i} sum_{y|j} sum_{d|(x, y)}mu(d) \ = & sum_{x = 1} sum_{y = 1} sum_{d|(x, y)}mu(d) leftlfloor frac n{x} rightrfloor leftlfloor frac n{y} rightrfloor \ = & sum_{d = 1}mu(d) sum_{x = 1} leftlfloor frac n{xd} rightrfloor sum_{y = 1} leftlfloor frac n{yd} rightrfloor end{aligned}]

Submission。