ユークリッドの互除法やエラストテネスの篩, 繰り返し二乗法の計算を勉強した.

線分上の格子点の個数

最大公約数-1がこの問題の解となる. ユークリッドの互除法を元にgcdを実装.


#include <iostream>
#include <vector>
using namespace std;
int x_1, x_2, y_1, y_2;
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
int main(int argc, char const *argv[]) {
    cin >> x_1 >> y_1 >> x_2 >> y_2;
    int x_diff = abs(x_1 - x_2);
    int y_diff = abs(y_1 - y_2);
    cout << gcd(x_diff, y_diff) - 1 << endl;
    return 0;
}

双六

ユークリッドの互除法を拡張する. ax+by=1を満たす整数x, yを探すには以下のようなスクリプトを書く.


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;
}

素数判定

素数かどうかは2 ~ √nまでを調べればよい.


// 素数判定
bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
// 約数の列挙
vector<int> divisor(int n) {
    vector<int> res;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) {
                res.push_back(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;
}

素数の個数

エラストテネスの篩と呼ばれるアルゴリズムを使って数える. 最小の素数の倍数をどんどん省いていく.


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

区間内の素数の個数

篩を2つ用いることで, 特定の区間の素数の個数を調べることができる. 区間[a, b)を調べる場合は, [2, √b)と[a, b)の篩を別々に作っておく.


const int MAX_N = 100000000;
const int MAX_SORT_B = 100000000;
typedef long long ll;
bool is_prime[MAX_N];
bool is_prime_small[MAX_SORT_B];
int a, b;
void segment_sieve(ll a, ll b) {
    for (int i = 0; (ll)i * i < b; i++) {
        is_prime_small[i] = true;
    }
    for (int i = 0; i < b - a; i++) {
        is_prime[i] = true;
    }
    for (int i = 2; (ll)i * i < b; i++) {
        if (is_prime_small[i]) {
            for (int j = 2 * i; (ll)j * j < b; j += i) {
                is_prime_small[j] = false;
            }
            for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) {
                is_prime[j - a] = false;
            }
        }
    }
}

Carmichael_Numbers

繰り返し二乗法を用いてべき乗を計算する. 基本的な考え方としてはx^22 = x^16 * x^4 * x^2のようにx^2^i
を順次求めながら計算する.


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

感想

最後のビット計算をうまく使う実装は自分でできる気がしない…