原理
在埃氏筛中,我们会发现一个合数我们会筛多次,浪费大量时间,因此我们就会考虑,能不能让每个数只被筛一次?也就引出了欧拉筛,也就是线性筛. 线性筛保证了每个数只被其最小的质因数晒去.我们考虑算术基本定理,,有,且 ,我们都用去筛掉这个数,从而达成线性时间复杂度
代码
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,下一个质数为 如果此时不break,那么下一个要被筛掉的数为 由,且p是从小到大枚举的,则p是筛掉i的第一个质因子 那么可以将i写为 代回得 欧拉筛法一定是用每个最小的质因子筛去这个数,target的最小质因子应该为p,说明此时应该break,等i增长为才能筛去这个数
线性筛求积性函数
如果用动态规划的观点去看,我们每次筛数的过程也可以将i的信息以及p一起转移到i*p上,因此可以用来求解积性函数.
线性筛求解莫比乌斯函数
若 为质数,则 。
在线性筛中,每个合数 都是被最小的质因子筛掉的。 设 是 的最小质因子,则 通过 筛掉。
-
若 能被 整除 () 则 也包含质因子 ,这意味着 包含至少两个质因子 (即 含有平方因子 )。 根据莫比乌斯函数的定义:
-
若 不能被 整除 () 则 比 多出一个不同的质因子 。 根据性质推导:
- 若 ,则
- 若 ,则
- 若 ,则
结论: 在这种情况下,
题意简述
给定 ,求满足以下条件的数对 的个数:
数据规模:
- 组询问,
莫比乌斯函数的性质
基本性质: 即:当 时,和为 ;当 时,和为 。
推导应用: 根据上述性质,我们可以将“最大公约数为 1”的条件转化为 函数的求和:
推导过程
阶段一:特殊情况(当 时)
目标:计算
- 代入 函数性质:
- 变换求和顺序(枚举 ):
- 利用整除个数公式: 由于 中 的倍数共有 个,故公式化简为:
该式可以使用 整除分块(数论分块)在 的时间内求解。
阶段二:一般情况(任意 )
目标:计算
- 变量替换: 令 ,则 。 同时,新的范围变为 :
- 代入阶段一的结论: 通过相同的推导过程:
- 得出最终公式:
代码
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);1. 问题定义
假设给定数组 包含 个正整数 。 我们需要计算满足 的数对 的数量(其中 )。
2. 引入莫比乌斯函数性质
代入上式:
3. 代入原式
将步骤 2 的等式代入 的定义中:
4. 交换求和顺序
目前的求和逻辑是:先枚举所有数对 ,再枚举它们 GCD 的因子 。 为了优化计算,我们需要交换求和顺序:先枚举可能的因子 ,再统计有多少对 的 GCD 是 的倍数。
是数组中元素的最大值(本题中为 )。
5. 简化计数条件
观察内部的求和条件:
这意味着 必须同时整除 和 。即 和 都必须是 的倍数。
我们定义 为输入数组中 的倍数的个数。
在内部求和中,我们需要从这 个倍数中,任意选出 2 个组成一对 (且 )。 根据组合数学,从 个元素中选 2 个的方案数为 。
因此,内部求和的值为:
6. 最终公式
将步骤 5 的结果代回步骤 4 的公式,得到最终的可计算公式:
代码
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;分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时