Sakana~
0%

数论4：线性筛，整除分块等

发表于 更新于 分类于

公式挂掉太丑了就看这里

数论4：线性筛，整除分块，求组合数基础等杂

线性筛

image-20221020162221317

$p[i]: $ $i$ 的最小素因子

$pr:$ 素数是哪些

整除分块

image-20221020170905725

long long 取模

估计商的取值

image-20221020172426748

exgcd例题

对于负数整除要写个函数，因为是向0取整

O(n)预处理求组合数

1
2
3
4
5
6
7
8
9
10
11
12
void pre () {
    fac[0] = 1;
    for (int i = 1; i <= N; i++)    fac[i] = fac[i-1] * i % mod;
    inv[N] = qmi (fac[N], mod - 2, mod);
    for (int i = N; i >= 1; i--)    inv[i - 1] = inv[i] * i % mod;
    assert (inv[0] == 1);
}
 
ll C (int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

分段打表求组合数

让可怜的本地机跑ε=ε=ε=(￣▽￣)

打表程序：

1
2
3
4
5
ll fac = 1;
for (int i = 1; i < mod; i++) {
    fac = fac * i % mod;
    if (i % 1000000 == 0)   printf ("%lld, ", fac);
}

image-20221021170201929

C. Ray Tracing

https://codeforces.com/contest/724/problem/C

image-20221021171506015

image-20221021172628897

区间筛

image-20221025182938142

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
p[1] = 1;
for (int i = 2; i <= N; i++) {
    if (!p[i])  p[i] = i, pr[++tot] = i;
    for (int j = 1; j <= tot && pr[j] * i <= N; j++) {
        p[i * pr[j]] = pr[j];
        if (p[i] == pr[j])  break;
    }
}

for (int j = 2; j <= tot; j++) {
    int p = pr[j];
    for (ll x = r / p * p; x >= l && x > p; x -= p) {
        vis[x - l] = true;
    }
}

for (ll i = max (2ll, l); i <= r; i++) {
    if (!vis[i - l]) {
        ans ^= (a * (uint) i + b);
    }
}