今回は paiza の「べき乗の計算」の問題に挑戦！
2進数を使ったアルゴリズムを学んだ！
問題概要
- 整数
Nが与えられる - 2 の
N乗を 1000003 で割った余り を求める。
入力例：
10
出力例：
1024
❌NG例：TLE
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
const N = Number(lines[0]);
const M = 2 ** N % 3;
console.log(M);
});
素直に * 2 を繰り返し行おうとすると、最大 10^12 回ループが回ることになってしまい、 実行制限時間に間に合わない。
✅OK例：
const rl = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
let N = BigInt(lines[0]);
const MOD = 1000003n;
let p = 2n; // 2^(2^i)
let ans = 1n;
while (N > 0n) {
if (N & 1n) {
ans = (ans * p) % MOD;
}
p = (p * p) % MOD;
N >>= 1n; // ビットシフト
}
console.log(ans.toString());
});
🔍 このコードの流れ
- 入力から
Nを読み取り、BigIntに変換する - 剰余用の定数
MOD = 1000003を用意する -
p = 2（今使える 2 のかたまり）を用意する -
ans = 1（答えをためる箱）を用意する
-
Nが0になるまでループ-
Nの最下位ビットを見る
→N & 1 - もし
1なら
→ans = ans × p (mod MOD)を行う -
pを平方して次の２のかたまりにする
→p = p × p (mod MOD) -
Nを右に 1 ビットずらす（Nを 2 で割る）
→N >>= 1
-
- ループ終了時、
ansに 2ⁿ mod 1000003 が入っている -
ansを文字列にして出力する
💡 繰り返し二乗法
2 ^ N を、 2 ^ (2 ^ i) 乗を用いて表すことで計算量を O(logN) に落とすアルゴリズム。
① 何をしたいアルゴリズム？
2 の N 乗を、高速に求めたい！
ただし、N は最大 10¹²。
2 × 2 × 2 × …（N回）
👉 これは無理 ❌
② 発想の転換①：指数を一気に増やす
毎回 2 を掛けるのではなく、
自分自身を掛ける（平方）。
2
2²
2⁴
2⁸
2¹⁶
...
1 回の計算で、指数が 2 倍になる。
👉 40 回くらいで 10¹² に到達。
※ 「平方（へいほう）」とは、ある数を「それ自身」と掛け合わせること。
例えば、5の平方なら5×5=25のことで、25が「5の平方」。
面積の単位「平方メートル（m²）」（1m×1m）のように、正方形の一辺の長さにちなんだ言葉でもある。
③ 発想の転換②：N を 2 進数で見る
N は人間には 10 進数で見えるけど、
コンピュータの中では最初から 2 進数。
例：
13 = 1101(2)
これは
13 = 8 + 4 + 1
という意味。
つまり
2¹³ = 2⁸ × 2⁴ × 2¹
👉 必要なのは「1 の桁」に対応するものだけ
④ 変数の役割
| 変数 | 役割 |
|---|---|
| N | 今どのビットを見ているか |
| p | そのビットに対応する 2 のかたまり |
| ans | 答えを作る箱 |
⑤ ループでやっていること
① 最下位ビットを見る
N & 1
- 1 は 000...001(2)
- AND を取ると 最下位ビットだけ残る
↓
-
1→ この桁は使う -
0→ 使わない
例：N = 13
N = 1101
1 = 0001
AND を取ると：
1101
& 0001
------
0001
👉 右端（最下位ビット）だけが残る
- 1 は 右端しか
1じゃない - 左の桁は全部
0 - AND(
&) は「両方1のときだけ1」
② ビットが 1 なら掛ける
ans = ans * p
👉 「この桁の分、答えに足す」
③ p を平方する
p = p * p
👉
- 今：2⁴
- 次：2⁸
次のビット用のかたまりを準備
⑥ 実際の流れ（2¹³）
N = 1101p = 2¹ans = 1
| ループ | N | N&1 | 処理 | p |
|---|---|---|---|---|
| 1 | 1101 | 1 | ans×2¹ | 2¹ |
| 2 | 110 | 0 | 何もしない | 2² |
| 3 | 11 | 1 | ans×2⁴ | 2⁴ |
| 4 | 1 | 1 | ans×2⁸ | 2⁸ |
⑦ なぜ速い？
- 毎回 N を 半分にする
- ループ回数は log₂N
- 最大でも約 40 回
👉 巨大な指数でも一瞬
⑧補足
補足① 毎回 % MOD する理由
ans = (ans * p) % MOD;
p = (p * p) % MOD;
% MODを毎回するのは、途中でも % MOD を取らないと、数が大きくなりすぎて破綻するから。
👉 途中で % MOD を取っても、最終結果は同じ。
(a * b) % m
= ((a % m) × (b % m)) % m
補足② n がつく理由
const MOD = 1000003n;
let p = 2n;
let ans = 1n;
1n や 2n の n は
「これは BigInt 型ですよ」という宣言。
BigInt 同士でしか計算できないルールがあるため揃える必要がある。
補足③ ans.toString()
console.log(ans.toString());
ans の型は BigInt。
出力時に n 付きで表示されることがある。
だから .toString() を使う。
-
BigInt→ 文字列 -
nが消える - 純粋な数値として出力できる
-
Number(ans)の場合、数値が巨大だと壊れる可能性がある。
補足④ ansの初期値
let ans = 1;
掛け算で答えを作っていくから、最初は 1 にしておく。
📝まとめ
N の 2 進数を右から見ながら、必要な 2 のかたまりだけ掛けていく処理。