因数に関する考察

• 1からnまでのすべての数の因数の総数はO(n log n)である。
• 1からnまでの素数の個数はO(n / log n)である。
• 伯トラン・チェビシェフの定理：n ≥ 1のとき、nと2nの間に少なくとも1つの素数がある。
• 直角三角形の辺の長さの一般式：a = w * 2uv, b = w * (u^2 - v^2), c = w * (u^2 + v^2)、ここでu, v, wは正の整数。

問題

• Common Divisors: a_1, a_2, ..., a_nの中で少なくとも2つがxの倍数となるxを見つける。
• Fair Warning: gcd(a_i + y, a_2 + y, ..., a_n + y) = g_yとすると、g_y | (a_i - a_j)、1 ≤ i, j ≤ nである。

最大公約数に関する考察

GCD

• gcd(a, b) = gcd(a, a + b) = gcd(a, b - a) = gcd(a, b mod a) = gcd(b, a mod b)
• gcd(ab, ac) = a * gcd(b, c)
• gcd(a, b) * lcm(a, b) = a * b

実装

template<typename T>
T gcd(T a, T b) {
    return (b == 0) ? a : gcd(b, a % b);
}

拡張ユークリッドのアルゴリズム (exGCD)

解法

方程式 ax + by = gcd(a, b)について、exGCDを用いて解を求める。

実装

template<typename T>
void exgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

同余に関する考察

同余類と縮同余類

• mod m の同余類: Z_m = {0̅, 1̅, ..., (m-1)̅}
• mod m の縮同余類: Z_m* = {x̅ | 0 ≤ x < m, gcd(x, m) = 1}

乗法的逆元

• a ∈ Z_m* (gcd(a, m) = 1) に対して、b ∈ Z_m* が存在し、a * b ≡ 1 (mod m)

計算方法

• フェルマーの小定理**: a^(p-1) ≡ 1 (mod p)、ここでpは素数で、pとaは互いに素。
• 拡張ユーオッドのアルゴリズム**: 同余方程式 a * x ≡ 1 (mod p) を解く。
• 階乗を利用した方法**: O(n + log V) で1からnまでの数の逆元を求める。
• 線形再帰による方法**: O(n) で1からnまでの数の逆元を求める。

const int MAX_N = 1000000;
long long d, f[MAX_N], val[MAX_N];
bitset<MAX_N> book;
vector<pair<int, long long>> pr;

void euler(int n) {
    book[0] = book[1] = 1;
    f[0] = 0, f[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!book[i]) {
            pr.emplace_back(i, pow(i, d));
            f[i] = pow(i, d) + 1;
            val[i] = i;
        }
        for (auto v : pr) {
            if (1LL * i * v.first > n) break;
            book[i * v.first] = 1;
            if (i % v.first == 0) {
                val[i * v.first] = val[i] * v.first;
                if (i == val[i])
                    f[i * v.first] = f[i] * v.second + 1;
                else
                    f[i * v.first] = f[i / val[i]] * f[val[i] * v.first];
                break;
            } else {
                val[i * v.first] = v.first;
                f[i * v.first] = f[i] * f[v.first];
            }
        }
    }
}