1934 字
10 分钟
原理

原理#

在埃氏筛中,我们会发现一个合数我们会筛多次,浪费大量时间,因此我们就会考虑,能不能让每个数只被筛一次?也就引出了欧拉筛,也就是线性筛. 线性筛保证了每个数只被其最小的质因数晒去.我们考虑算术基本定理,∀n∈N\forall n \in \mathbb{N},有n=p1r1p2r2…psrsn=p_1^{r_1}p_2^{r_2}\dots p_s^{r_s},且p1<p2<⋯<pnp_1<p_2<\dots<p_n ∀n\forall n,我们都用p1p_1去筛掉这个数,从而达成线性时间复杂度

代码#

洛谷模板

vector<ll> primes;
vector<bool> vis;
auto euler = [&](int n) {
vis.assign(n + 10, 0);
for (int i = 2; i <= n; i++) {
if (!vis[i])
primes.push_back(i);
for (auto p : primes) {
if (i * p > n)
break;
vis[i * p] = 1;
if (i % p == 0)
break;
}
}
};

这里为什么要有i%p==0? 考虑当前从小到大枚举到了i,质数p,下一个质数为pnextp_{next} 如果此时不break,那么下一个要被筛掉的数为 Target=i⋅pnextTarget=i\cdot p_{next} 由p∣ip|i,且p是从小到大枚举的,则p是筛掉i的第一个质因子 那么可以将i写为i=p⋅mi=p\cdot m 代回得Target=p⋅m⋅pnext=p⋅(m⋅pnext)Target=p\cdot m\cdot p_{next}=p\cdot (m\cdot p_{next}) 欧拉筛法一定是用每个最小的质因子筛去这个数,target的最小质因子应该为p,说明此时应该break,等i增长为m⋅pnextm\cdot p_{next}才能筛去这个数

线性筛求积性函数#

如果用动态规划的观点去看,我们每次筛数的过程也可以将i的信息以及p一起转移到i*p上,因此可以用来求解积性函数.

线性筛求解莫比乌斯函数 μ\mu#

若 ii 为质数,则 μ(i)=−1\mu(i) = -1。

在线性筛中,每个合数 mm 都是被最小的质因子筛掉的。 设 pjp_j 是 mm 的最小质因子,则 mm 通过 m=i×pjm = i \times p_j 筛掉。

  1. 若 ii 能被 pjp_j 整除 (i(modpj)=0i \pmod{p_j} = 0) 则 ii 也包含质因子 pjp_j,这意味着 m=i×pjm = i \times p_j 包含至少两个质因子 pjp_j(即 mm 含有平方因子 pj2p_j^2)。 根据莫比乌斯函数的定义: μ(m)=0\mu(m) = 0

  2. 若 ii 不能被 pjp_j 整除 (i(modpj)≠0i \pmod{p_j} \neq 0) 则 mm 比 ii 多出一个不同的质因子 pjp_j。 根据性质推导:

    • 若 μ(i)=−1\mu(i) = -1,则 μ(m)=1\mu(m) = 1
    • 若 μ(i)=1\mu(i) = 1,则 μ(m)=−1\mu(m) = -1
    • 若 μ(i)=0\mu(i) = 0,则 μ(m)=0\mu(m) = 0

结论: 在这种情况下,μ(m)=−μ(i)\mu(m) = -\mu(i)


P3455 [POI 2007] ZAP-Queries

题意简述#

给定 n,m,kn, m, k,求满足以下条件的数对 (i,j)(i, j) 的个数: ∑i=1n∑j=1m[gcd⁡(i,j)=k]\sum_{i=1}^n \sum_{j=1}^m [\gcd(i, j) = k]

数据规模:

  • 1≤k≤n,m≤5×1041 \le k \le n, m \le 5 \times 10^4
  • TT 组询问,T=5×104T = 5 \times 10^4

莫比乌斯函数的性质#

基本性质: ∑d∣nμ(d)=[n=1]\sum_{d|n} \mu(d) = [n = 1] 即:当 n=1n=1 时,和为 11;当 n>1n>1 时,和为 00。

推导应用: 根据上述性质,我们可以将“最大公约数为 1”的条件转化为 μ\mu 函数的求和: [gcd⁡(i,j)=1]=∑d∣gcd⁡(i,j)μ(d)[\gcd(i, j) = 1] = \sum_{d|\gcd(i, j)} \mu(d)


推导过程#

阶段一:特殊情况(当 k=1k=1 时)#

目标:计算 ∑i=1n∑j=1m[gcd⁡(i,j)=1]\sum_{i=1}^n \sum_{j=1}^m [\gcd(i, j) = 1]

  1. 代入 μ\mu 函数性质: ∑i=1n∑j=1m∑d∣gcd⁡(i,j)μ(d)\sum_{i=1}^n \sum_{j=1}^m \sum_{d|\gcd(i, j)} \mu(d)
  2. 变换求和顺序(枚举 dd): ∑d=1min⁡(n,m)μ(d)∑i=1n[d∣i]∑j=1m[d∣j]\sum_{d=1}^{\min(n, m)} \mu(d) \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j]
  3. 利用整除个数公式: 由于 1…n1 \dots n 中 dd 的倍数共有 ⌊nd⌋\lfloor \frac{n}{d} \rfloor 个,故公式化简为: ∑d=1min⁡(n,m)μ(d)⌊nd⌋⌊md⌋\sum_{d=1}^{\min(n, m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor

该式可以使用 整除分块(数论分块)在 O(n)O(\sqrt{n}) 的时间内求解。


阶段二:一般情况(任意 kk)#

目标:计算 ∑i=1n∑j=1m[gcd⁡(i,j)=k]\sum_{i=1}^n \sum_{j=1}^m [\gcd(i, j) = k]

  1. 变量替换: 令 i=i⋅k,j=j⋅ki = i \cdot k, j = j \cdot k,则 gcd⁡(i,j)=k  ⟺  gcd⁡(ik,jk)=k  ⟺  gcd⁡(i,j)=1\gcd(i, j) = k \iff \gcd(ik, jk) = k \iff \gcd(i, j) = 1。 同时,新的范围变为 i∈[1,⌊n/k⌋],j∈[1,⌊m/k⌋]i \in [1, \lfloor n/k \rfloor], j \in [1, \lfloor m/k \rfloor]: ∑i=1⌊n/k⌋∑j=1⌊m/k⌋[gcd⁡(i,j)=1]\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} [\gcd(i, j) = 1]
  2. 代入阶段一的结论: 通过相同的推导过程: ∑i=1⌊n/k⌋∑j=1⌊m/k⌋∑d∣gcd⁡(i,j)μ(d)\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d|\gcd(i, j)} \mu(d)
  3. 得出最终公式: ∑d=1⌊n/k⌋μ(d)⌊nkd⌋⌊mkd⌋\sum_{d=1}^{\lfloor n/k \rfloor} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor

代码

cin >> n;
vector<ll> primes;
bitset<N> vis;
vector<ll> mu(N + 5, 0);
auto init = [&]() {
mu[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i])
primes.push_back(i), mu[i] = -1;
for (auto p : primes) {
if (i * p > N)
break;
vis[i * p] = 1;
if (i % p == 0) {
mu[i * p] = 0;
break;
} else {
mu[i * p] = -mu[i];
}
}
}
for (int i = 1; i <= N; i++)
mu[i] += mu[i - 1];
};
init();
auto cal = [&](ll a, ll b, ll d) {
if (a > b)
swap(a, b);
a /= d, b /= d;
ll res = 0;
for (ll l = 1, r; l <= a; l = r + 1) {
r = min(a / (a / l), b / (b / l));
res += (mu[r] - mu[l - 1]) * (a / l) * (b / l);
}
return res;
};
while (n--) {
ll a, b, d;
cin >> a >> b >> d;
cout << cal(a, b, d) << '\n';
}

P2158 [SDOI2008] 仪仗队 类似的题目,将原点看作(0,0),从1开始计数直到n-1,对(0,1)与(1,0)特殊讨论,注意n=1

vector<ll> primes;
bitset<N> vis;
vector<ll> mu(N + 5, 0);
auto init = [&]() {
mu[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i])
primes.push_back(i), mu[i] = -1;
for (auto p : primes) {
if (i * p > N)
break;
vis[i * p] = 1;
if (i % p == 0) {
mu[i * p] = 0;
break;
} else {
mu[i * p] = -mu[i];
}
}
}
for (int i = 1; i <= N; i++)
mu[i] += mu[i - 1];
};
init();
auto cal = [&](ll n) {
ll res = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = (n / (n / l));
res += (mu[r] - mu[l - 1]) * (n / l) * (n / l);
}
return res;
};
cin >> n;
cout << cal(n - 1) + (n == 1 ? 0 : 2);

CSES Counting Coprime Pairs

1. 问题定义#

假设给定数组 AA 包含 nn 个正整数 x1,x2,…,xnx_1, x_2, \dots, x_n。 我们需要计算满足 gcd⁡(xi,xj)=1\gcd(x_i, x_j) = 1 的数对 (i,j)(i, j) 的数量(其中 1≤i<j≤n1 \le i < j \le n)。

2. 引入莫比乌斯函数性质#

代入上式:

[gcd⁡(xi,xj)=1]=∑d∣gcd⁡(xi,xj)μ(d)[\gcd(x_i, x_j) = 1] = \sum_{d | \gcd(x_i, x_j)} \mu(d)

3. 代入原式#

将步骤 2 的等式代入 AnsAns 的定义中:

Ans=∑1≤i<j≤n(∑d∣gcd⁡(xi,xj)μ(d))Ans = \sum_{1 \le i < j \le n} \left( \sum_{d | \gcd(x_i, x_j)} \mu(d) \right)

4. 交换求和顺序#

目前的求和逻辑是:先枚举所有数对 (i,j)(i, j),再枚举它们 GCD 的因子 dd。 为了优化计算,我们需要交换求和顺序:先枚举可能的因子 dd,再统计有多少对 (i,j)(i, j) 的 GCD 是 dd 的倍数。

Ans=∑d=1Vμ(d)×∑1≤i<j≤n[d∣gcd⁡(xi,xj)]Ans = \sum_{d=1}^{V} \mu(d) \times \sum_{1 \le i < j \le n} [d | \gcd(x_i, x_j)]

VV 是数组中元素的最大值(本题中为 10610^6)。

5. 简化计数条件#

观察内部的求和条件:

[d∣gcd⁡(xi,xj)][d | \gcd(x_i, x_j)]

这意味着 dd 必须同时整除 xix_i 和 xjx_j。即 xix_i 和 xjx_j 都必须是 dd 的倍数。

我们定义 cnt[d]cnt[d] 为输入数组中 dd 的倍数的个数。

cnt[d]=∑k=1n[d∣xk]cnt[d] = \sum_{k=1}^{n} [d | x_k]

在内部求和中,我们需要从这 cnt[d]cnt[d] 个倍数中,任意选出 2 个组成一对 (i,j)(i, j)(且 i<ji < j)。 根据组合数学,从 mm 个元素中选 2 个的方案数为 (m2)\binom{m}{2}。

因此,内部求和的值为:

∑1≤i<j≤n[d∣gcd⁡(xi,xj)]=(cnt[d]2)=cnt[d]×(cnt[d]−1)2\sum_{1 \le i < j \le n} [d | \gcd(x_i, x_j)] = \binom{cnt[d]}{2} = \frac{cnt[d] \times (cnt[d] - 1)}{2}

6. 最终公式#

将步骤 5 的结果代回步骤 4 的公式,得到最终的可计算公式:

Ans=∑d=1Vμ(d)×cnt[d]×(cnt[d]−1)2Ans = \sum_{d=1}^{V} \mu(d) \times \frac{cnt[d] \times (cnt[d] - 1)}{2}

代码

cin >> n;
vector<ll> s(n + 5, 0);
vector<ll> primes;
vector<ll> mu(N + 5, 0);
vector<ll> cnt(N + 5, 0);
unordered_map<ll, ll> nums;
auto euler = [&]() {
bitset<N + 5> vis;
mu[1] = 1;
for (ll i = 2; i <= N; i++) {
if (!vis[i]) {
primes.push_back(i), mu[i] = -1;
}
for (auto x : primes) {
if (i * x > N)
break;
vis[i * x] = 1;
if (i % x == 0) {
mu[i * x] = 0;
break;
} else {
mu[i * x] = -mu[i];
}
}
}
};
euler();
for (int i = 1; i <= n; i++)
cin >> s[i], nums[s[i]]++, ma = max(ma, s[i]);
for (ll d = 1; d <= ma; d++) {
for (ll j = d; j <= ma; j += d) {
if (nums.count(j))
cnt[d] += nums[j];
} // 由调和级数为nlogn复杂度
}
for (int i = 1; i <= ma; i++) {
ans += mu[i] * (cnt[i] - 1) * cnt[i] / 2;
}
cout << ans;
原理
https://sanzenin.top/posts/obsidian/欧拉筛法-线性筛/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取