繰り返し二乗法 (Binary Exponentiation)

繰り返し二乗法は、べき乗の計算（$x^n \pmod m$）を効率的に行う手法です。標準的な pow 関数よりも高速であり、大きな数に対する余り（mod）の計算を安全に行うことができます。

アルゴリズムの原理

指数 $n$ を 2 進数として分解することで、計算回数を $O(n)$ から $O(\log n)$ に削減します。例えば、$x^{10}$ を計算する場合、$10$ は 2 進数で $1010_2$ です。これは以下のように展開できます。

$$x^{10} = x^{2^3} \times x^{2^1} = x^8 \times x^2$$

実装例（反復法）

long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        // 指数の最下位ビットが1の場合、現在のベースを結果に掛ける
        if (exp & 1) {
            result = (__int128)result * base % mod;
        }
        // ベースを自乗し、指数を右シフトする
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

高速乗算 (Binary Multiplication)

2 つの大きな数の積を求める際に、そのまま計算すると long long 型の範囲を超えてオーバーフローする場合があります。このアルゴリズムは、べき乗の計算と同様の原理を「加算」に応用することで、オーバーフローを回避しながら $a \times b \pmod m$ を計算します。

実装例

long long safe_mul(long long a, long long b, long long m) {
    long long res = 0;
    a %= m;
    while (b > 0) {
        if (b & 1) {
            res = (res + a) % m;
        }
        a = (a + a) % m;
        b >>= 1;
    }
    return res;
}

進数変換 (Base Conversion)

数値の表現を異なる進数に変換する処理は、プログラミングにおける基本的な操作の一つです。

1. 任意の進数から10進数への変換

各桁の数字に対して、その桁の重み（基数のべき乗）を掛けて合計します。Horner法（ホーナー法）を用いると、効率的に実装できます。

long long to_decimal(string s, int base) {
    long long res = 0;
    for (char c : s) {
        int val;
        if (isdigit(c)) val = c - '0';
        else val = toupper(c) - 'A' + 10;
        res = res * base + val;
    }
    return res;
}

2. 10進数から任意の進数への変換

数値を基数で割り続け、その余りを逆順に並べることで変換を行います。

string from_decimal(long long n, int base) {
    if (n == 0) return "0";
    string res = "";
    while (n > 0) {
        int rem = n % base;
        if (rem < 10) res += (char)('0' + rem);
        else res += (char)('A' + rem - 10);
        n /= base;
    }
    reverse(res.begin(), res.end());
    return res;
}

総合的な変換処理の例

以下は、$N$ 進数の数値を読み取り、それを $M$ 進数に変換して出力するプログラムの構造です。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int src_base, target_base;
    string num_str;

    if (!(cin >> src_base >> num_str >> target_base)) return 0;

    // 一旦10進数に変換
    long long dec_val = 0;
    for (char c : num_str) {
        dec_val *= src_base;
        if (c >= '0' && c <= '9') dec_val += (c - '0');
        else dec_val += (toupper(c) - 'A' + 10);
    }

    // 10進数から目的の進数へ変換
    if (dec_val == 0) {
        cout << "0" << endl;
    } else {
        string result = "";
        while (dec_val > 0) {
            int r = dec_val % target_base;
            result += (r < 10) ? (char)('0' + r) : (char)('A' + r - 10);
            dec_val /= target_base;
        }
        reverse(result.begin(), result.end());
        cout << result << endl;
    }

    return 0;
}