繰り返し二乗法、高速乗算、および進数変換のアルゴリズム実装
繰り返し二乗法 (Binary Exponentiation)
繰り返し二乗法は、べき乗の計算（$x^n \pmod m$）を効率的に行う手法です。標準的な pow 関数よりも高速であり、大きな数に対する余り（mod）の計算を安全に行うことができます。
アルゴリズムの原理
指数 $n$ を 2 進数として分解することで、計算回数を $O(n)$ から $O(\log n)$ に削減します。例えば、$x^{10}$ を計算する場 ...
9月20日 10:59 投稿
100から999の間で各桁の積と和が等しい数値を表示し合計数をカウントする方法
100〜999の範囲にある3桁の数字のうち、各桁（一の位、十の位、百の位）の乗算結果が各桁の加算結果と一致する数値とその総数を出力する処理について説明します。
アルゴリズムの実装手順
1. 全ての3桁の数値を走査するループを構築します。
for (int num = 100; num < 1000; num++)
2. 各桁の値を抽出する必要があります。
例として数値472を考えます
472 / 1 == 4 ...
9月9日 09:06 投稿
AtCoder Beginner Contest 357 における A から D 問題の解法解説
問題A: Sanitizer
N人の人が順番に手を消毒します。各人が必要とする消毒液の量 $H_i$ が与えられ、合計 $M$ 単位の消毒液があるとき、何人目までが完全に手を消毒できるかを求める問題です。
実装としては、配列に格納された各 $H_i$ を順に累積し、その合計が $M$ を超えた時点のインデックスを確認します。累積和が $M$ を超えない場合は、全員が消毒可能です。
#inclu ...
7月1日 16:24 投稿
桁の和がsとなるn桁の正整数の個数を求める
これは条件付きの正整数分割問題であり、直接的な計算式は存在しません。
小規模な場合は全探索が可能です。数百桁規模になると動的計画法が有効です。しかし数千桁規模では動的計画法でも数十分から数時間要します。さらに万桁規模になると、時間・空間的な制約によりPCでの計算は不可能になります。
「挿入法と包含排除原理の組み合わせ」が強力な手法です。
核心となる ...
5月12日 17:53 投稿