素因数分解

void factorize(int n, vector<int>& primes) {
    for (int d = 2; 1LL * d * d <= n; ++d) {
        if (n % d == 0) {
            primes.push_back(d);
            while (n % d == 0) n /= d;
        }
    }
    if (n > 1) primes.push_back(n);
}

ユークリッドの互除法による GCD / LCM

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
long long lcm(long long x, long long y) { return x / gcd(x, y) * y; }

フェルマーの小定理を用いた逆元計算

mod が素数のとき、a / b mod p は a * b^(p-2) mod p と書ける。

const long long MOD = 19260817;

long long mod_pow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

long long inv(long long b) {
    return mod_pow(b, MOD - 2, MOD);
}

整数二分探索の 2 パターン

// 左側を残すパターン
int lower(int l, int r) {
    while (l < r) {
        int m = (l + r) / 2;
        if (check(m)) r = m;
        else l = m + 1;
    }
    return l;
}

// 右側を残すパターン
int upper(int l, int r) {
    while (l < r) {
        int m = (l + r + 1) / 2;
        if (check(m)) l = m;
        else r = m - 1;
    }
    return l;
}

座標圧縮 (Coordinate Compression)

vector<int> zip(vector<int> raw) {
    vector<int> xs = raw;
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int& v : raw)
        v = lower_bound(xs.begin(), xs.end(), v) - xs.begin();
    return raw;
}

二次元累積和

using ll = long long;
const int MAX = 1010;
ll s[MAX][MAX];

ll query(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

void build(int n, int m) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> s[i][j];
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }
}

環状配分問題 (HAOI2008 チョコレート配布)

中央値を使って最小移動量を求める。

long long solve() {
    int n; cin >> n;
    vector<long long> a(n), c(n+1);
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    long long ave = sum / n;
    for (int i = 1; i <= n; ++i)
        c[i] = c[i-1] + a[i-1] - ave;
    sort(c.begin()+1, c.end());
    long long med = c[(n+1)/2], res = 0;
    for (int i = 1; i <= n; ++i)
        res += abs(c[i] - med);
    return res;
}

基数変換 (任意進数変換)

string convert(const string& num, int from, int to) {
    vector<int> digits;
    for (char c : num) {
        if (isdigit(c)) digits.push_back(c - '0');
        else if (isupper(c)) digits.push_back(10 + c - 'A');
        else digits.push_back(36 + c - 'a');
    }
    reverse(digits.begin(), digits.end());

    vector<int> res;
    while (!digits.empty()) {
        int rem = 0;
        for (int i = digits.size()-1; i >= 0; --i) {
            digits[i] += rem * from;
            rem = digits[i] % to;
            digits[i] /= to;
        }
        res.push_back(rem);
        while (!digits.empty() && digits.back() == 0) digits.pop_back();
    }
    reverse(res.begin(), res.end());

    string ans;
    for (int v : res) {
        if (v < 10) ans += '0' + v;
        else if (v < 36) ans += 'A' + v - 10;
        else ans += 'a' + v - 36;
    }
    return ans;
}

数論的ブロック (Floor Sum 高速化)

long long floor_sum(long long n, long long k) {
    long long res = n * k;
    for (long long l = 1, r; l <= n; l = r + 1) {
        r = k / l ? min(n, k / (k / l)) : n;
        res -= (k / l) * (r - l + 1) * (l + r) / 2;
    }
    return res;
}

ディリクレ前処理 (Dirichlet Prefix Sum)

void dirichlet(vector<unsigned>& f) {
    int n = f.size() - 1;
    vector<bool> vis(n+1, false);
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;
        for (int j = 1; i * j <= n; ++j) {
            f[i*j] += f[j];
            vis[i*j] = true;
        }
    }
}

区間マージ

bool merge(const vector<pair<int,int>>& segs) {
    vector<pair<int,int>> tmp = segs;
    sort(tmp.begin(), tmp.end());
    int ed = tmp[0].second;
    for (size_t i = 1; i < tmp.size(); ++i) {
        if (tmp[i].first <= ed) ed = max(ed, tmp[i].second);
        else return false;
    }
    return true;
}

多路マージ (優先度付きキュー)

int fishing(int n, int T, vector<int> a, vector<int> d, vector<int> t) {
    priority_queue<pair<int,int>> pq;
    for (int i = 0; i < n; ++i)
        pq.emplace(a[i], i);
    int res = 0;
    for (int step = 0; step < T; ++step) {
        auto [val, id] = pq.top(); pq.pop();
        res += val;
        val = max(0, val - d[id]);
        pq.emplace(val, id);
    }
    return res;
}

増加部分列の個数 (DP)

int count_lis(const string& s) {
    int n = s.size();
    vector<int> dp(n, 1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (s[j] < s[i]) dp[i] += dp[j];
            else if (s[j] == s[i]) dp[j] = 0;
        }
    }
    return accumulate(dp.begin(), dp.end(), 0);
}

約数の総和 (高速等比級数和)

const int MOD = 9901;

int geo_sum(int p, int k) {
    if (k == 0) return 1;
    if (k % 2 == 0)
        return (1LL + 1LL * p * geo_sum(p, k-1)) % MOD;
    return 1LL * geo_sum(p, k/2) * (1 + pow_mod(p, k/2 + 1, MOD)) % MOD;
}

int sum_of_divisors(int n, int k) {
    int res = 1;
    for (int p = 2; p * p <= n; ++p) {
        if (n % p) continue;
        int cnt = 0;
        while (n % p == 0) { n /= p; ++cnt; }
        res = 1LL * res * geo_sum(p, cnt * k) % MOD;
    }
    if (n > 1) res = 1LL * res * geo_sum(n, k) % MOD;
    return res;
}

Fenwick Tree (Binary Indexed Tree)

template<typename T>
struct Fenwick {
    vector<T> bit;
    int n;
    Fenwick(int n) : n(n), bit(n+1) {}
    void add(int idx, T delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    T sum(int idx) {
        T res = 0;
        for (; idx; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    T range(int l, int r) { return sum(r) - sum(l-1); }
};