アルゴリズム図鑑 ~ 整数

1. Euclidean Algorithm

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    cout << euclidean(a, b) << endl;
}

2. Extend Euclidean Algorithm

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    int x, y;
    cout << euclidean(a, b, x, y) << endl;
    cout << x << " " << y << endl;
}

3. Eratosthenes

#include <iostream>
#include <vector>
using namespace std;

vector<int> primeEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    vector<int> result;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) result.push_back(i);
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    for (auto num : primeEratosthenes(n)) {
        cout << num << endl;
    }
}

4. Chinese Remainder Theorem

#include <iostream>
#include <vector>
using namespace std;

// 拡張ユークリッド互除法：a*x + b*y = gcd(a, b)
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int x1, y1;
    int g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// aの逆元 mod m を求める（aとmは互いに素）
int modinv(int a, int m) {
    int x, y;
    int g = extended_gcd(a, m, x, y);
    if (g != 1) {
        throw runtime_error("modular inverse does not exist");
    }
    return (x % m + m) % m;
}

// 中国剰余定理：x ≡ a_i (mod m_i) の解を求める
int chinese_remainder(const vector<int>& a, const vector<int>& m) {
    int n = a.size();
    long long M = 1;
    for (int i = 0; i < n; ++i) M *= m[i];

    long long result = 0;
    for (int i = 0; i < n; ++i) {
        long long Mi = M / m[i];
        int inv = modinv(Mi % m[i], m[i]); // mod m[i] における逆元
        result += 1LL * a[i] * Mi * inv;
    }

    return (result % M + M) % M; // 正の最小解
}

int main() {
    // x ≡ 2 mod 3
    // x ≡ 3 mod 5
    // x ≡ 2 mod 7
    vector<int> a = {2, 3, 2};
    vector<int> m = {3, 5, 7};

    cout << "x ≡ " << chinese_remainder(a, m) << " mod " << (3 * 5 * 7) << endl;
    // 出力: x ≡ 23 mod 105
}