問題敘述

給一大小 $N$ 的序列，回答 $M$ 次查詢，每次查詢都是問一個區間 $[L, R]$ 的答案（比如區間眾數）

使用條件

1. 可以在很短的時間內由 $[L, R]$ 得到 $[L, R + 1], [L - 1, R], [L, R - 1], [L + 1, R]$ 的答案
2. 可以離線運算（也就是可以把輸入通通吃進來再輸出）

算法

將 $M$ 次查詢根據 $L$ 的大小分為 $\sqrt{N}$ 塊
也就是每塊裡面的 $L$ 最多只會差距 $\sqrt{N}$
每塊裡面的 $R$ 再由小到大排序
按照排好的順序算答案，缺少什麼就一個個加進來，多了什麼就一個個丟掉
add 函式就是實作把一個數加進目前的區間
sub 函式就是實作把一個數從目前的區間丟掉

1
2
3
4
5
6

struct Q {
    int l, r, b, i;
    bool operator < (const Q &q) {
        return b == q.b ? (r < q.r) : b < q.b;
    }
} q[MAXM];

1
2
3
4
5
6
7
8
9
10
11

int block = ceil(sqrt(MAXN));

for (int i = 0; i < m; i++) {
    int l, r; cin >> l >> r;
    q[i].l = l;
    q[i].r = r;
    q[i].b = q[i].l / block;
    q[i].i = i;
}

sort(q, q + m);

1
2
3
4
5
6
7

for (int i = 0, L = 0, R = -1; i < m; i++) {
    while (R < q[i].r) add(a[++R]);
    while (q[i].l < L) add(a[--L]);
    while (q[i].r < R) sub(a[R--]);
    while (L < q[i].l) sub(a[L++]);
    ans[q[i].i] = cur;
}

時間複雜度

$O(N^{1.5})$

奇偶優化

第一塊的 $R$ 從小到大
第二塊從 $R$ 大到小
第三塊從 $R$ 小到大
在從第一塊要到第二塊的時候，$R$ 都是大的
在從第二塊要到第三塊的時候，$R$ 都是小的

1
2
3

bool operator < (const Q &q) {
    return b == q.b ? (r < q.r) ^ (b % 2) : b < q.b;
}

題目

Codeforces 86D - Powerful array

1. http://sunmoon-template.blogspot.com/2015/08/mos-algorithm.html
2. https://zhuanlan.zhihu.com/p/25017840
3. https://oi-wiki.org/misc/mo-algo/

Bloom Filter

用來快速搜尋資料是否存在於資料庫

我們的資料庫是一個 $2^m$ 大小的陣列

1

db = [False] * (2 ** m)

加資料進資料庫

我們有 $k$ 個 hash function 的輸出都是一個 $m$ bits 的數 ( $< 2^m$ )

把資料 $x$ 加進資料庫就是等於，將 $x$ 的各個雜湊值的位置設成 True

1
2

for i in range(k):
    db[hash[k](x)] = True

查詢資料是否在資料庫裡

查詢資料 $x$ 是否在資料庫裡

1
2
3
4

if all([db[hash[k](x)] for i in range(k)]):
    # 資料 x 可能在資料庫裡
else:
    # 資料 x 一定不在資料庫裡

1. http://www.evanlin.com/BloomFilter/
2. http://bryanpendleton.blogspot.com/2011/12/three-papers-on-bloom-filters.html

有一個奇合數 $n$ ，是兩個奇質數的乘積 $n = pq$
令 $a = \frac{p + q}{2}, b = \frac{p - q}{2}$ 那麼 $n = (a + b)(a - b) = a^2 - b^2$
但是今天我們不知道 $p, q$ ，而我們想要分解 $n$
那我們就猜 $a = \lceil \sqrt{n} \rceil$ ，測試 $a^2 - n$ 是不是完全平方數
猜到的話可以從 $a, b$ 反推回 $p, q$
沒猜到就把 $a$ 加一繼續猜

使用條件

當 $|p-q|$ 很小，可以有效的分解合數 $n$

程式碼 ( python )

1
2
3
4
5
6
7
8
9
10
11

import math
import gmpy2

def fermat(n):
    a = math.ceil(math.sqrt(n))
    b2 = a * a - n
    while not gmpy2.iroot(b2, 2)[1]:
        a = a + 1
        b2 = a * a - n
    b = math.sqrt(b2)
    return [a + b, a - b]

有一個合數 $n$，有一個質因數 $p$
Pollard’s p - 1 algorithm 可以在 $p-1$ 的最大質因數很小的情況下，有效的分解合數 $n$
可以用在分解 RSA 產生的公鑰 $n$，以此破解 RSA，常見於一些 CTF 的題目中

根據費馬小定理
當 $a$ 不是 $p$ 的倍數
$a^{p-1} \equiv 1 \pmod{p} \to a^{k(p-1)} \equiv 1 \pmod{p} \to a^{k(p-1)} - 1 \equiv 0 \pmod{p}$ for some $k$
所以 $gcd(a^{k(p-1)} - 1, n)$ 一定會是 $p$ 的倍數

Pollard’s p - 1 algorithm 就是嘗試去構造出 $k(p-1)$ ，並且令 $a = 2$ ( 只要 $p \ne 2$ 上面的推論就是對的 )
也就是測試 $gcd(2^{1} - 1, n), gcd(2^{1 \times 2} - 1, n), gcd(2^{1 \times 2 \times 3} - 1, n), …$
當 $1 \times 2 \times 3 \cdots$ 是 $p-1$ 的倍數，我們就成功分解 $n$

使用條件

當 $p-1$ 最大的質因數很小，可以有效的分解合數 $n$

程式碼 ( python )

1
2
3
4
5
6
7
8
9

import math

def pollard(n):
    a, b = 2, 2
    while True:
        a, b = pow(a, b, n), b + 1
        d = math.gcd(a - 1, n)
        if 1 < d < n:
            return d