文学徒が競プロをするブログ

競技プログラミングの精進を記録していきます

練習がてら数学系ライブラリを実装した

はじめに

競プロは実質数学ゲーというのはよく言われるところですが、整数に関してよく出る処理はライブラリとしてまとめておいた方がいいなと思い実装し始めました。
現在実装できているのは

以上の5つです。
あとコンビネーション(4C2 = 6 とかそんな感じのアレ)は書いておこうと思います。くるさん(水色er)にも用意しておいた方がいいと言われましたので。
もしそれ以外で何かおすすめだったりネタだったりがありましたら、DMかコメントをいただければと思います。

ライブラリはGitHub (https://github.com/sarashinanikki/library-of-competitive-programing) に置いているので適当にご覧ください。

解説

ここからは、それぞれのライブラリについての解説を書きます。

最大公約数(gcd)

2つの数の最大公約数を出すライブラリです。配列を投げれば3つ以上の最大公約数も求められます。大抵の言語には既にあるライブラリですが、とりあえず書きました。

考え方

ユークリッドの互除法を用います。詳細を知りたければググるか、神サイト『高校数学の美しい物語』を見てください。ユークリッドってすごいなあという気持ちになれます。

コード

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

この短さで最大公約数が爆速で求められるんだからすごいなあと思いませんか？私は思います。

最小公倍数(lcm)

2つの数の最小公倍数を求めるライブラリです。実質gcdです。

考え方

最小公倍数は2つの数の積を最大公約数で割ると出るので、ライブラリ化する必要は正直ないかと思いましたがせっかくなので作りました。

コード

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

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

†実質gcd†

エラトステネスのふるい

素数列挙アルゴリズムの一つです。Nを入力するとO(N log log N)でNまでの素数を列挙してくれます。
妙な書き方ですが、O(N log log N)らしいです。詳しいことはググるか以下略。

考え方

Nの二乗根までの素数を全列挙して、それらのNまでの倍数を消していくと素数が残ります。
bool配列を使うとうまく実装できます。

コード

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

vector<int> primes;

void erathosthenes(int n) {
    bool primeFlags[n+1];
    for (int i = 0; i <= n; i++) {
        primeFlags[i] = true;
    }
    primeFlags[0] = primeFlags[1] = false;
    vector<int> sqrtprimes;
    for (int i = 2; i*i <= n; i++) {
        bool mod0 = false;
        for (int j = 2; j*j <= i; j++) {
            if (i%j == 0) mod0 = true;
        }
        if (!mod0) sqrtprimes.push_back(i);
    }
    for (int i = 0; i < sqrtprimes.size(); i++) {
        for (int j = 2; j <= n; j++) {
            if (j%sqrtprimes[i] == 0) primeFlags[j] = false;
        }
    }
    for (int i = 0; i < sqrtprimes.size(); i++) primeFlags[sqrtprimes[i]] = true;
    for (int i = 1; i <= n; i++) {
        if (primeFlags[i]) primes.push_back(i);
    }
    return;
}

コメントを一切入れていないと死ぬほど見づらいですね。ごめんなさい。あとエラトステネスの綴を間違えています。eratosthenesですね。
ちなみにbool配列で数字を持つ関係上、競プロだと106くらいでMLEします(多分)。

素因数分解

エラトステネスのふるいで素数が全列挙できたので、素因数分解ができます。

考え方

NをNまでの素数で割っていき、割り切れた回数をMapで保持します。

コード

// --------------以下ライブラリ-------------------//

#include <iostream>
#include <utility>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <numeric>
#include <sstream>
typedef long long ll;
using namespace std;

vector<int> primes;
map<int, int> factors;

void erathosthenes(int n) {
    bool primeFlags[n+1];
    for (int i = 0; i <= n; i++) {
        primeFlags[i] = true;
    }
    primeFlags[0] = primeFlags[1] = false;
    vector<int> sqrtprimes;
    for (int i = 2; i*i <= n; i++) {
        bool mod0 = false;
        for (int j = 2; j*j <= i; j++) {
            if (i%j == 0) mod0 = true;
        }
        if (!mod0) sqrtprimes.push_back(i);
    }
    for (int i = 0; i < sqrtprimes.size(); i++) {
        for (int j = 2; j <= n; j++) {
            if (j%sqrtprimes[i] == 0) primeFlags[j] = false;
        }
    }
    for (int i = 0; i < sqrtprimes.size(); i++) primeFlags[sqrtprimes[i]] = true;
    for (int i = 1; i <= n; i++) if (primeFlags[i]) primes.push_back(i);
    return;
}

void factoring(int n) {
    erathosthenes(n);
    for (int i = 0; i < primes.size(); ++i) {
        while(n%primes[i] == 0){
            factors[primes[i]]++;
            n /= primes[i];
        }
    }
}


//------------------以下debug用main関数-----------------------//


int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    factoring(n);
    cout << "Primes =" << " ";
    for (auto x : primes) cout << x << " ";
    cout << "" << std::endl;
    string factorString = "factoring = ";
    for (auto x : factors) factorString +=  to_string(x.first) + "^" + to_string(x.second) + " * ";
    for (int i = 0; i < 3; i++) factorString.pop_back();
    cout << factorString << std::endl;
    return 0;
}

出来ているかの確認をするためにmain関数を追加しています。これをコピペしてもらえばそのまま動くはずです。
ちなみにやたらincludeが多いのは、競プロ用のテンプレを流用し始めたからです。

階乗の素因数分解

素因数分解が出来ると、階乗の素因数分解が出来ます。この間のD問題にも出てましたね。

考え方

2からNまでの数を全て素因数分解してやり、それを合わせると階乗の素因数分解になります。

コード

// --------------以下ライブラリ------------------//

#include <iostream>
#include <utility>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <numeric>
#include <sstream>
typedef long long ll;
using namespace std;

vector<int> primes;
map<int, int> factors;

void erathosthenes(int n) {
    bool primeFlags[n+1];//boolでふるいを用意する。素数であればtrueであるとする
    for (int i = 0; i <= n; i++) primeFlags[i] = true;//ふるいをリセット
    primeFlags[0] = primeFlags[1] = false;//0と1は素数ではないのでふるい落とす(=falseにする)
    vector<int> sqrtprimes;//ルートnまでの素数を入れておくための配列
    for (int i = 2; i*i <= n; i++) {
        bool mod0 = false;
        for (int j = 2; j*j <= i; j++) {
            if (i%j == 0) mod0 = true;
        }
        if (!mod0) sqrtprimes.push_back(i);
    }
    for (int i = 0; i < sqrtprimes.size(); i++) {
        for (int j = 2; j <= n; j++) {
            if (j%sqrtprimes[i] == 0) primeFlags[j] = false;
        }
    }
    for (int i = 0; i < sqrtprimes.size(); i++) primeFlags[sqrtprimes[i]] = true;
    for (int i = 1; i <= n; i++) if (primeFlags[i]) primes.push_back(i);
    return;
}

void factoring(int n) {
    for (int i = 0; i < primes.size(); ++i) {
        while(n%primes[i] == 0){
            factors[primes[i]]++;
            n /= primes[i];
        }
    }
}

void factorial(int n) {
    erathosthenes(n);
    for (int i = 2; i <= n; ++i) {
        factoring(i);
    }
}

//---------以上ライブラリ--------//----------以下debug用main関数----------//


int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    factorial(n);
    cout << "Primes =" << " ";
    for (auto x : primes) cout << x << " ";
    cout << "" << std::endl;
    string factorString = "factoring = ";
    for (auto x : factors) factorString +=  to_string(x.first) + "^" + to_string(x.second) + " * ";
    for (int i = 0; i < 3; i++) factorString.pop_back();
    cout << factorString << std::endl;
    return 0;
}

はい。まあ使う機会が来ることを願っています。
あとエラトステネスのふるいは大きい数だとMLEするので、更にスマートな素数列挙アルゴリズムを考える必要があるかもしれません。

追記予定

  • コンビネーション