zak 讲数论专题,好难,听不懂,整理一下。
借鉴了 zak 的课件。
还没写完呐,还会更新的。
一、线性筛
筛出 \(n\) 以内的所有质数。
\(n ≤ 10^8\)。
直接埃氏筛是 \(O(n \ln \ln n)\) 的,但是一个合数会被筛多次,所以需要优化。线性筛时考虑一个合数只被它的最小因数 \(p\) 筛,设合数为 \(xp\),先枚举 \(x\),再枚举 \(p\),如果 \(x \bmod p = 0\),那么 \(xp\) 就不是最小因数,就跳出循环,每个合数只会被筛一次,时间复杂度 \(O(n)\)。
const int N = 1e8 + 5;
int n, ip[N], p[N], cnt;
void init() {
ip[1] = 1;
FOR(i, 2, n) {
if(!ip[i]) {
p[++cnt] = i;
}
for(int j = 1; j <= cnt && i * p[j] <= n; j++) {
ip[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
二、Dirichlet 前缀和
给定数组 \(a\),求数组 \(b\) 满足 \(b_{x} = \sum_{y|x}a_y\)。
\(n \le 2\times 10^7\)。
直接做是 \(O(n \ln n)\) 的,无法通过,考虑优化。这个式子可以进行转化,把 \(A\) 和 \(B\) 看作数组 \(a\) 和 \(b\) 的数论函数,那么通过 Dirichlet 卷积得出 \(A*I=B\),把题面转化为求 \(A\) 与 \(I\) Dirichlet 卷积的前 \(n\) 位。然后考虑如何计算,先将积性函数 \(I\) 拆分成一堆积性函数,设 \(p_i\) 为第 \(i\) 大的素数,定义 \(f_i(p^k)=[p=p_i]\),那么 \(I = \prod f_i\),所以题目又转化为 \(B=A*\prod f_i\),这可以直接埃氏筛计算,时间复杂度 \(O(n \ln \ln n)\)。
const int N = 2e7 + 5;
int n;
uint a[N]; int p[N];
void solve() {
cin >> n >> seed;
FOR(i, 1, n) a[i] = rnd();
uint ans = 0;
p[1] = 1;
FOR(i, 1, n) {
if(!p[i]) {
for(int j = 1; i * j <= n; j++) {
a[i * j] += a[j];
p[i * j] = 1;
}
}
ans ^= a[i];
}
cout << ans << endl;
}
三、整除分块
求 \(\sum_{i=1}^{n}d(i)\)。
\(n \le 10^{12}\)。
先推导式子 \(\sum_{i=1}^{n}d(i)=\sum_{i=1}^{n}\sum_{xy=i}1=\sum_{xy\le n}1=\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\)。而 \(\lfloor \frac{n}{i} \rfloor\) 只有 \(O(\sqrt{n})\) 种取值,且每种取值连续,考虑一起计算,对于一个左端点 \(l\) 找出连续值的最右端点 \(r\),就是 \(\lfloor \frac{n}{r} \rfloor \ge \lfloor \frac{n}{l} \rfloor\) 的最大的 \(r\),也就是 \(\left \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \right \rfloor\),时间复杂度 \(O(\sqrt{n})\)。
ll n, ans;
void solve() {
cin >> n;
for(ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}
cout << ans << endl;
}
四、莫比乌斯函数
例一
给定序列 \(A, B, C\),求 \(\sum_{i=1}^{n}\sum_{j=1}^{n} A(i)B(j)C(\gcd(i, j))\)。
\(n \le 10^6\)。
先枚举 \(\gcd\)。
\[\sum_{i=1}^{n}\sum_{j=1}^{n} A(i)B(j)C(\gcd(i, j)) \]\[=\sum_{g=1}^{n}C(g) \sum_{i=1}^{\lfloor\frac{n}{g}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{g}\rfloor} A(ig)B(jg)[\gcd(i,j)=1]\]然后替换 \(\gcd\) 为 \(\mu\) 函数然后提出来。
\[=\sum_{g=1}^{n}C(g) \sum_{i=1}^{\lfloor\frac{n}{g}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{g}\rfloor} A(ig)B(jg) \sum_{t|i,t|j}\mu(t)\]\[=\sum_{g=1}^{n} \sum_{t=1}^{\lfloor\frac{n}{g}\rfloor} C(g)\mu(t) (\sum_{i=1}^{\lfloor\frac{n}{gt}\rfloor}A(igt)) (\sum_{j=1}^{\lfloor\frac{n}{gt}\rfloor} B(jgt))\]把 \(C\) 和 \(\mu\) 卷起来,设 \(D(x)=\sum_{d|x}C(x)\mu(\frac{x}{d})\)。
\[=\sum_{k=1}^{n} D(k) (\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}A(ik)) (\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} B(jk))\]可以 \(O(n \ln n)\) 或者 \(O(n \ln \ln n)\) 实现。
标签:lfloor,frac,数论,18,sum,rfloor,2024,ln,int From: https://www.cnblogs.com/kevinlikescoding/p/18018779