【競プロ整数ライブラリ】蟻本 2-6章 まとめ

蟻本2-6章を読んで素数・約数系のライブラリ的なものができたのでまとめておきます。説明は全部蟻本にあるぞい。

【なかみ】

• gcd(a, b): aとbの最大公約数
• lcm(a, b): aとbの最小公倍数
• extgcd(a, b, &x, &y): ax + by = gcd(a,b) の解(x,y)を得る(拡張ユーグリッド互除法)
• is_prime(n): 素数判定
• vector divisor(n): 約数のvectorを返す
• map<int, int> prime_factor(n): 素因数分解(2⁵*3² = {2:5, 3:2}みたいな感じで返ってくる)
• sieve(n): エラトステネスのふるい(nまでの素数表を作る)
• count_prime(a, b): [a, b)内の素数の個数を返す
• mod_pow(x, n, mod): xⁿ % modを高速演算
• getFib(k): k番目までのフィボナッチ数を求める(2016/02/10 19:18 追加)

(2016/02/09 23:17 追記) ご指摘をいただいたのですが、lcmは a * b / gcd(a, b) ではなく a / gcd(a, b) * b と先に割った方がいいみたいです！（オーバーフローを防ぐため）そのように改訂させていただきました。

(2016/02/10 20:03 追記) getFibは 1, 2, 3, 5, 8, ...　の順になっています。1, 1, 2, 3, 5,...としたい場合はif文2つを以下のように書き換えてください。（k=2の場合はループで計算されるので不要）

    if (k == 0 || k == 1) return 1;

(2016/02/12 18:35 追記) getFibは行列を用いるとで実装可能です！(蟻本 p.180)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b ;
}

int extgcd(int a, int b, int& x, int& y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

vector<int> divisor(int n) {
    vector<int> res;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.pb(i);
            if (i != n / i) res.pb(n / i);
        }
    }
    return res;
}

map<int, int> prime_factor(int n) {
    map<int, int> res;
    for(int i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

const int MAX_N = 10000000;
int prime[MAX_N];
bool memo[MAX_N + 1];

int sieve(int n) {
    int p = 0;
    REP(i ,n) memo[i] = true;
    memo[0] = memo[1] = false;
    for (int i = 2; i <= n; i++) {
        if (memo[i]) {
            prime[p++] = i;
            for (int j = 2 * i; j <= n; j += i) memo[j] = false;
        }
    }
    return p;
}

typedef long long ll;

const ll MAX_LEN = 1000000;
const ll MAX_SQRT_B = 1000000;
bool memo_all[MAX_LEN];         //i means i + a
bool memo_small[MAX_SQRT_B];

ll count_prime(ll a, ll b) {
    for (int i = 0; (ll)i * i < b; i++) memo_small[i] = true;
    for (int i = 0; i < b - a; i++)     memo_all[i] = true;

    for (int i = 2; (ll)i * i < b; i++) {
        if (memo_small[i]) {
            for (int j = 2; (ll)j * j < b; j += i) memo_small[j] = false;
            for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) memo_all[j - a] = false;
        }
    }

    ll ret = 0;
    for (ll i = a; i < b; i++) {
        if (memo_all[i]) ret++;
    }
    return ret;
}

ll mod_pow(ll x, ll n, ll mod) {
    if (n == 0) return 1;
    ll res = mod_pow(x * x % mod, n / 2, mod);
    if (n & 1) res = res * x % mod;
    return res;
}

const int MAX_FIB_LEN = 100000;
ll fibdp[MAX_FIB_LEN];
ll getFib(int k) {
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (fibdp[k] != 0) return fibdp[k];
    return fibdp[k] = getFib(k-1) + getFib(k-2);
}