Problem link ও উৎস
- **Original source:** CP-Algorithms — Binary Exponentiation
- **Platform:** CP-Algorithms —
, CSES Exponentiation —
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Medium
- **Pattern:** square & multiply (binary exponentiation)
- **Basic idea inherited from:** 028 — Modular Multiplication (প্রতি গুণে mod)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তিনটে সংখ্যা `a` (base), `b` (exponent, `b ≥ 0`), আর `m` (`m > 0`) দেওয়া। বের করতে হবে `a^b % m` — মানে `a`-কে নিজে দিয়ে `b` বার গুণ, তারপর mod m।
আসল challenge: `b` বিশাল হতে পারে (10¹⁸ পর্যন্ত)। `a`-কে `b` বার গুণলে loop `b` বার ঘোরে — ও পথে মহাবিশ্বের আয়ু শেষ। চাই `O(log b)`-তে উত্তর।
### Input ও output {#6-example-input-and-output}
```text
a b m -> a^b % m check
-----------------------------------------------
3 13 7 -> 3 3^13 = 1594323, % 7 = 3
2 10 1000 -> 24 1024 % 1000 = 24
5 0 13 -> 1 যেকোনো^0 = 1
7 1 100 -> 7 a^1 = a
2 100 ... -> বিশাল O(log) তেও ঝটপট
10 5 1 -> 0 mod 1 = সব 0!
```
edge case দুটো খেয়াল করো: **b = 0 হলে উত্তর 1** (যেকোনো সংখ্যার শূন্যতম power 1), আর **m = 1 হলে উত্তর সবসময় 0** (এক ঘরের ঘড়ি)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমাকে একটা কাগজ **8 বার ভাঁজ** করতে হবে। এক এক ভাঁজ করলে 8 বার খাটতে হয়। কিন্তু চালাকি: এক ভাঁজ করলে 2 স্তর, সেটা আবার ভাঁজ করলে 4, আবার করলে 8 — মাত্র **3** বারেই 8 স্তর! প্রতিবার আগেরটা **দ্বিগুণ** হচ্ছে।
power-ও তেমন: `a`-কে square করলে exponent দ্বিগুণ হয় (`a → a² → a⁴ → a⁸`)। তাই 8 power পেতে 8 গুণ নয়, 3 square যথেষ্ট। আর exponent যদি ঠিক 2-এর power না হয় (যেমন 13), তখন মাঝে মাঝে দরকারি টুকরোগুলো (`a^8, a^4, a^1`) আলাদা করে জমিয়ে রাখি — সেটাই "multiply" ধাপ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **028 — Modular Multiplication** থেকে। binary exponentiation-এর প্রতিটা ধাপ — square (`a = a*a % m`) আর multiply (`result = result*a % m`) — দুটোই 028-এর "প্রতি গুণে mod" নিয়ম।
028 না থাকলে এখানে মাঝের সংখ্যা বিশাল হয়ে overflow/slowness হতো। আর exponent-কে binary-তে ভাঙার idea-টা Level 0-এর "শেষ bit দেখা" (`b & 1`) আর "bit shift" (`b >> 1`)-এর সাথে যুক্ত — পুরনো tool নতুন কাজে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **binary exponentiation (square-and-multiply)**। exponent-কে binary-তে ভাবো।
যেমন `13 = 1101₂ = 8 + 4 + 1`, তাই:
`a^13 = a^8 × a^4 × a^1`
আর `a^1, a^2, a^4, a^8` — প্রতিটা আগেরটার **square**:
`a^2 = (a^1)²`, `a^4 = (a^2)²`, `a^8 = (a^4)²`
মানে: base-কে বারবার square করো, আর exponent-এর binary-তে যেখানে যেখানে bit 1, সেখানকার power-টা উত্তরে গুণে নাও। প্রতি step-এ 028-এর modular multiplication। `b`-এর binary-তে bit সংখ্যা `log₂(b)` — তাই **O(log b)** ধাপ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল: `a`-কে `b` বার গুণো, প্রতি step-এ mod।
```python
def power_brute(a, b, m):
result = 1
for _ in range(b):
result = result * a % m # b বার গুণ
return result
```
ঠিক উত্তর দেয়, আর প্রতি step-এ mod নেওয়ায় সংখ্যা ছোটও থাকে। সমস্যা শুধু একটাই — loop চলে `b` বার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে ঠিক `b` বার। `b = 10^18` হলে 10^18 বার গুণ — সেকেন্ডে 10^8-10^9 operation ধরলেও কয়েকশো বছর লাগবে। interview/CP-তে এটা অসম্ভব।
```text
b = 10^18 হলে:
brute (O(b)): 10^18 বার গুণ -> কার্যত অসম্ভব
binary (O(log b)): ~60 বার গুণ -> চোখের নিমেষে
log2(10^18) ≈ 60 -> পার্থক্য: 10^18 vs 60
```
মূল শিক্ষা: exponent linearly না কমিয়ে **প্রতি step-এ অর্ধেক** করো (binary)। তাহলেই O(b) → O(log b)।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
exponent-কে binary ভেবে square-and-multiply চালাই: base বারবার square করো; exponent-এর last bit 1 হলে current base-টা result-এ গুণো; তারপর exponent-কে ডানে shift (অর্ধেক) করো।
```python
def power_mod(a, b, m):
result = 1
a %= m # base আগে ঘড়িতে নামাই
while b > 0:
if b & 1: # exponent-এর last bit 1?
result = result * a % m # এই power-টা উত্তরে নাও
a = a * a % m # base square করো (exponent দ্বিগুণ হলো)
b >>= 1 # পরের bit-এ যাও (exponent অর্ধেক)
return result
```
প্রতি iteration-এ `b` অর্ধেক হয় — তাই মোটে `log₂(b)` বার ঘোরে। প্রতিবার একটা square, কখনো একটা multiply — সব 028-এর modular multiplication।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **exponent-কে এক করে না কমিয়ে binary-তে ভাবো — প্রতি step-এ base square হলে exponent দ্বিগুণ "ঢাকা" পড়ে।** তাই `b` বার গুণের বদলে `log b` বার square যথেষ্ট, মাঝে মাঝে দরকারি টুকরো তুলে রেখে।
দুটো ছোট tweak মনে রাখো:
- শুরুতেই `a %= m` — base বড় হলে আগেই ছোট করে নাও।
- `b & 1` (last bit পড়া) + `b >>= 1` (অর্ধেক করা) — Level 0-এর bit tool-ই এখানকার চাবি।
### ছবিতে বোঝা {#5-visual-explanation}
`3^13 % 7` — 13-কে binary-তে ভাঙা:
```text
13 = 1101₂ = 8 + 4 + 1
3^13 = 3^8 × 3^4 × 3^1 (যেখানে bit 1, সেই power নেব)
bit: 1 1 0 1 <- 13 = 1101, ডান থেকে পড়ি: 1,0,1,1
power: 3^8 3^4 3^2 3^1
নেব? হ্যাঁ হ্যাঁ না হ্যাঁ
```
square করে করে এগোনো (mod 7):
```text
3^1 = 3
3^2 = 3^1 × 3^1 = 9 % 7 = 2
3^4 = 3^2 × 3^2 = 4 % 7 = 4 (2×2)
3^8 = 3^4 × 3^4 = 16 % 7 = 2 (4×4)
উত্তর = 3^8 × 3^4 × 3^1 = 2 × 4 × 3 = 24 % 7 = 3
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`power_mod(3, 13, 7)` — 13 = 1101₂:
| step | b (binary) | last bit (b&1) | result | a (square হয়ে) |
| --- | --- | --- | --- | --- |
| শুরু | 1101 | — | 1 | 3 % 7 = 3 |
| 1 | 1101 | 1 | 1×3 % 7 = 3 | 3×3 % 7 = 2 |
| 2 | 110 | 0 | 3 (অপরিবর্তিত) | 2×2 % 7 = 4 |
| 3 | 11 | 1 | 3×4 % 7 = 5 | 4×4 % 7 = 2 |
| 4 | 1 | 1 | 5×2 % 7 = 3 | 2×2 % 7 = 4 |
`b` এখন 0, loop থামল। উত্তর **3**। Check: 3^13 = 1594323 = 7×227760 + 3 ✓।
লক্ষ করো: step 1-এ bit 1 → result-এ গুণ; step 2-এ bit 0 → শুধু square, result অপরিবর্তিত। আর `a` প্রতি step-এ square হয়ে 3 → 2 → 4 → 2 (= 3^1, 3^2, 3^4, 3^8 mod 7)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def power_mod(a, b, m):
"""a^b % m, square-and-multiply দিয়ে O(log b)। b >= 0, m > 0।"""
result = 1
a %= m
while b > 0:
if b & 1: # last bit 1 হলে এই power নাও
result = result * a % m
a = a * a % m # base square
b >>= 1 # exponent অর্ধেক
return result
def power_brute(a, b, m):
"""যাচাইয়ের জন্য সরল O(b) version।"""
result = 1
for _ in range(b):
result = result * a % m
return result
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert power_mod(3, 13, 7) == 3 # 3^13 % 7
assert power_mod(2, 10, 1000) == 24 # 1024 % 1000
assert power_mod(5, 0, 13) == 1 # যেকোনো^0 = 1
assert power_mod(7, 1, 100) == 7 # a^1 = a
assert power_mod(10, 5, 1) == 0 # mod 1 -> 0
# Python-এর built-in pow(a, b, m) এর সাথে মিলিয়ে দেখা:
assert power_mod(3, 13, 7) == pow(3, 13, 7)
assert power_mod(2, 1000, 1000000007) == pow(2, 1000, 1000000007)
assert power_mod(123456, 789, 1000000007) == pow(123456, 789, 1000000007)
# brute force-এর সাথেও ছোট input-এ মিল:
assert power_mod(3, 13, 7) == power_brute(3, 13, 7)
assert power_mod(2, 20, 97) == power_brute(2, 20, 97)
print(power_mod(3, 13, 7)) # 3
print(power_mod(2, 10, 1000)) # 24
print(power_mod(2, 1000, 1000000007)) # বড় উত্তর, ঝটপট
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
result = 1
a %= m
```
`result` শুরু 1 (গুণের identity)। `a %= m`-এ base আগেই ঘড়িতে নামাই, যাতে পরের গুণগুলো ছোট থাকে।
```text
while b > 0:
if b & 1:
result = result * a % m
```
`b > 0` যতক্ষণ চলে। `b & 1` দেখে exponent-এর **last bit** 1 কিনা — হলে current `a` (যেটা এখন `a^(2^k)` রূপ) result-এ গুণে নিই। এটাই "multiply" ধাপ, প্রতি গুণে `% m`।
```text
a = a * a % m
b >>= 1
```
`a = a * a % m` — base square, মানে exponent এখন দ্বিগুণ ঢাকা পড়ল (`a^1 → a^2 → a^4 ...`)। `b >>= 1` — exponent-কে ডানে shift, অর্থাৎ অর্ধেক, পরের bit-এ যাওয়া।
`assert ... == pow(a, b, m)` লাইনগুলো Python-এর built-in তিন-argument `pow`-এর সাথে মিলিয়ে দেখছে — এটাই সবচেয়ে শক্ত যাচাই। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
3
24
... (একটা বড় সংখ্যা)
সব test pass!
```
প্রথম লাইন `power_mod(3, 13, 7)` → 3। দ্বিতীয় `power_mod(2, 10, 1000)` → 24 (1024 mod 1000)। তৃতীয় `power_mod(2, 1000, 1000000007)` → একটা বড় সংখ্যা, কিন্তু O(log b)-তে চোখের নিমেষে। আগের সব `assert` (built-in `pow`-এর সাথে মিল সহ) চুপচাপ pass — তারপর `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
এখানে `a * a` সহজেই 2^53 ছাড়িয়ে যায় (যেমন mod ~10⁹ হলে গুণফল ~10¹⁸), তাই সাধারণ `number`-এ নির্ভুলতা হারায় — `BigInt` দিয়ে লিখি।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// a^b % m — square-and-multiply, BigInt-এ (b >= 0, m > 0)
function powMod(a, b, m) {
a = BigInt(a); b = BigInt(b); m = BigInt(m);
let result = 1n;
a %= m; // base আগে ঘড়িতে নামাই
while (b > 0n) {
if (b & 1n) result = (result * a) % m; // last bit 1 → এই power নাও
a = (a * a) % m; // base square
b >>= 1n; // exponent অর্ধেক
}
return result;
}
// ---- test cases (file-এর example + edge case) ----
assert(powMod(3, 13, 7) === 3n, "3^13%7");
assert(powMod(2, 10, 1000) === 24n, "1024%1000");
assert(powMod(5, 0, 13) === 1n, "যেকোনো^0=1");
assert(powMod(7, 1, 100) === 7n, "a^1=a");
assert(powMod(10, 5, 1) === 0n, "mod 1 → 0");
// বড় mod-এও নির্ভুল (BigInt বলে overflow নেই)
assert(powMod(2, 1000, 1000000007) === 688423210n, "2^1000 mod 1e9+7");
assert(powMod(123456, 789, 1000000007) === 182677862n, "123456^789 mod 1e9+7");
console.log("সব JS test pass!");
```
> **JS টীকা:** সাধারণ `number`-এ `a * a % m` করলে m বড় হলে (mod ~10⁹) গুণফল ~10¹⁸ > 2^53 — silently ভুল উত্তর। তাই modular exponentiation-এ **BigInt** (`1n`, `b & 1n`, `b >>= 1n`) লাগে; literal-এ `n` suffix ভুলো না। (Python বড় int নিজেই সামলায় বলে সেখানে এটা লাগে না।)
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function powMod(aIn: number | bigint, bIn: number | bigint, mIn: number | bigint): bigint {
let a = BigInt(aIn), b = BigInt(bIn);
const m = BigInt(mIn);
let result = 1n;
a %= m;
while (b > 0n) {
if (b & 1n) result = (result * a) % m;
a = (a * a) % m;
b >>= 1n;
}
return result;
}
function expect(actual: bigint, expected: bigint, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const cases: ReadonlyArray