Number Theory

數論題常見的瓶頸不是單次計算，而是同一種操作會被查很多次：反覆分解質因數、計算模反元素，或在小質數模數下查組合數。這頁把這些操作整理成預處理加查詢的模板，方便在題目需要大量呼叫時直接套用。

Sieve of Eratosthenes

Sieve of Eratosthenes 常用來預處理質數資訊。若題目需要反覆分解質因數，可以改成預處理 spf，也就是每個數的 smallest prime factor。之後分解一個數 x 時，只要沿著 spf[x] 不斷往下除即可。

時間複雜度

• SPF 預處理：O(n log log n)
• 分解單一數字：約 O(log x)

模板

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> build_spf(int mx) {
    vector<int> spf(mx, 0);

    for (int i = 2; i < mx; ++i) {
        if (spf[i] != 0) continue;

        spf[i] = i;
        for (long long j = 1LL * i * i; j < mx; j += i) {
            if (spf[j] == 0) {
                spf[j] = i;
            }
        }
    }

    return spf;
}

vector<int> distinct_prime_factors(int x, const vector<int>& spf) {
    vector<int> primes;

    while (x > 1) {
        int p = spf[x];
        primes.push_back(p);

        while (x % p == 0) {
            x /= p;
        }
    }

    return primes;
}

參考題型

• LeetCode - Largest Component Size by Common Factor：先用 spf 找出每個數的 distinct prime factors。若兩個 index 共享同一個 prime factor，就用 DSU 合併到同一個 component。

C++

class DSU {
public:
    vector<int> parent, sz;

    DSU(int n) {
        parent.resize(n);
        sz.assign(n, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;

        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }

    int size(int x) {
        return sz[find(x)];
    }
};

class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        const int mx = 100000 + 1;

        vector<int> spf = build_spf(mx);
        vector<int> first(mx, -1);
        DSU dsu(nums.size());

        for (int i = 0; i < (int)nums.size(); ++i) {
            for (int p : distinct_prime_factors(nums[i], spf)) {
                if (first[p] == -1) {
                    first[p] = i;
                } else {
                    dsu.unite(i, first[p]);
                }
            }
        }

        int ans = 1;
        for (int i = 0; i < (int)nums.size(); ++i) {
            ans = max(ans, dsu.size(i));
        }

        return ans;
    }
};

Fermat's Little Theorem

若 mod 是質數，且 a 不是 mod 的倍數，根據 Fermat's little theorem：

\[ a^{mod - 1} \equiv 1 \pmod{mod} \]

因此：

\[ a^{-1} \equiv a^{mod - 2} \pmod{mod} \]

這常用來在質數模數下計算 modular inverse，例如組合數或多重集合排列數。

時間複雜度

• Fast power：O(log e)，其中 e 是指數
• Modular inverse under prime mod：O(log mod)
• Factorial / inverse factorial 預處理：O(n)
• 查詢組合數或 multinomial count：O(1)，另加字元統計成本

模板

C++

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll mod = 1000000007;

ll mod_pow(ll a, ll e) {
    a %= mod;
    ll ret = 1;

    while (e > 0) {
        if (e & 1) {
            ret = ret * a % mod;
        }
        a = a * a % mod;
        e >>= 1;
    }

    return ret;
}

ll mod_inv(ll a) {
    return mod_pow(a, mod - 2);
}

vector<ll> fact, inv_fact;

void build_factorials(int n) {
    fact.assign(n + 1, 1);
    inv_fact.assign(n + 1, 1);

    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % mod;
    }

    inv_fact[n] = mod_inv(fact[n]);
    for (int i = n; i >= 1; --i) {
        inv_fact[i - 1] = inv_fact[i] * i % mod;
    }
}

ll multinomial_count(const string& s) {
    array<int, 26> cnt{};

    for (char ch : s) {
        ++cnt[ch - 'a'];
    }

    ll ret = fact[s.size()];
    for (int x : cnt) {
        ret = ret * inv_fact[x] % mod;
    }

    return ret;
}

參考題型

• LeetCode - Count Anagrams：每個 word 的排列數是 len! / (cnt[0]! cnt[1]! ... cnt[25]!)。因為模數是質數，分母可以用 Fermat's little theorem 轉成 modular inverse。

C++

class Solution {
public:
    int countAnagrams(string s) {
        build_factorials(s.size());

        stringstream ss(s);
        string word;
        ll ans = 1;

        while (ss >> word) {
            ans = ans * multinomial_count(word) % mod;
        }

        return ans;
    }
};

Lucas Algorithm + CRT

Lucas algorithm 用來計算質數模數下的組合數：

\[ C(n, k) \bmod p \]

當目標模數不是質數時，可以先拆成互質模數，例如 10 = 2 * 5，分別計算 mod 2 和 mod 5 的結果，再用 Chinese remainder theorem 合併。

時間複雜度

• Lucas algorithm：此模板為 O(log_p n * p * log p)；若先預處理小組合數表，可降為 O(log_p n)
• CRT 合併兩個互質模數：O(log mod)，主要成本在 modular inverse

模板

C++

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll mod_pow(ll a, ll e, ll mod) {
    a %= mod;
    ll ret = 1 % mod;

    while (e > 0) {
        if (e & 1) {
            ret = ret * a % mod;
        }
        a = a * a % mod;
        e >>= 1;
    }

    return ret;
}

ll mod_inv_prime(ll a, ll mod) {
    return mod_pow(a, mod - 2, mod);
}

int comb_small(int n, int k, int mod) {
    if (n < k) return 0;

    int ret = 1;
    for (int i = 1; i <= k; ++i) {
        ret = 1LL * ret * (n - i + 1) % mod;
        ret = 1LL * ret * mod_inv_prime(i, mod) % mod;
    }

    return ret;
}

int lucas(int n, int k, int mod) {
    int ret = 1;

    while (n > 0 || k > 0) {
        int ni = n % mod;
        int ki = k % mod;

        if (ni < ki) return 0;

        ret = ret * comb_small(ni, ki, mod) % mod;
        n /= mod;
        k /= mod;
    }

    return ret;
}

int crt(int a, int m1, int b, int m2) {
    ll m = 1LL * m1 * m2;

    ll part1 = 1LL * a * m2 % m * mod_inv_prime(m2, m1) % m;
    ll part2 = 1LL * b * m1 % m * mod_inv_prime(m1, m2) % m;

    return (part1 + part2) % m;
}

參考題型

• LeetCode - Check If Digits Are Equal in String After Operations II：操作後每個位置的係數會對應到 binomial coefficient。因為最後只需要 mod 10，可以先用 Lucas algorithm 算 mod 2 和 mod 5，再用 CRT 合併。

C++

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size() - 1;
        int acc = 0;

        for (int i = 0; i < n; ++i) {
            int c2 = lucas(n - 1, i, 2);
            int c5 = lucas(n - 1, i, 5);
            int coef = crt(c2, 2, c5, 5);

            int diff = s[i + 1] - s[i];
            acc = (acc + coef * diff) % 10;
            if (acc < 0) acc += 10;
        }

        return acc == 0;
    }
};