Problem link ও উৎস
- **Original source:** Classic exercise (cyclicity of powers / last digit pattern)
- **Platform:** Classic exercise — math olympiad আর CP intro-তে সাধারণ
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Easy
- **Pattern:** cycle in powers (cyclicity)
- **Basic idea inherited from:** 026 — Remainder Basics (clock model)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা base `b` আর একটা বিশাল exponent `e` দেওয়া। বের করতে হবে `b^e`-এর **শেষ অঙ্ক** (last digit) — মানে `b^e % 10`। অথবা আরও সাধারণভাবে: `b^e % m` যখন `e` এত বড় যে সরাসরি power বের করা কঠিন।
মূল চাবি: power-এর remainder গুলো একসময় **পুনরাবৃত্তি** করে — একটা চক্র (cycle) তৈরি হয়। সেই চক্রের দৈর্ঘ্য জানলে, `e`-কে চক্র-দৈর্ঘ্য দিয়ে mod করে সরাসরি উত্তর পাওয়া যায়।
### Input ও output {#6-example-input-and-output}
```text
b e -> last digit (b^e % 10) চক্র
---------------------------------------------------------
7 222 -> 9 [7,9,3,1], 222%4=2 -> ঘর 2
2 10 -> 4 [2,4,8,6], 10%4=2 -> ঘর 2
3 4 -> 1 [3,9,7,1], 4%4=0 -> শেষ ঘর
5 100 -> 5 [5], cycle length 1
6 7 -> 6 [6], length 1
0 5 -> 0 0^e = 0 (e>0)
1 999 -> 1 [1], length 1
```
edge case: base-এর last digit 0,1,5,6 হলে cycle length 1 (সবসময় একই অঙ্ক)। `b^0 = 1`। আর remainder 0 হলে চক্রের শেষ ঘর — সবচেয়ে কমন ভুল এখানেই।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো **সপ্তাহের দিন**। আজ যদি সোমবার হয়, 100 দিন পরে কী বার? তুমি 100 দিন এক এক করে গুনবে না — জানো সপ্তাহ 7 দিনে চক্র; তাই `100 % 7 = 2`, সোমবার থেকে 2 দিন পরে = বুধবার। চক্রটা ধরেই লাফ দিলে।
power-এর last digit-ও তেমন: 7-এর power-এর শেষ অঙ্ক 7, 9, 3, 1, তারপর আবার 7, 9, 3, 1 — 4 দিনের "সপ্তাহ"। তাই `7^222`-এর শেষ অঙ্ক জানতে 222 বার গুণতে হয় না; `222 % 4` দিয়ে চক্রের ঘর বের করলেই হলো। বিশাল exponent ছোট চক্রে নেমে আসে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **026 — Remainder Basics** থেকে — clock model। mod m-এ ঘর সসীম (m টা), তাই power-এর remainder ঘুরেফিরে ফিরবেই — cyclicity-র পুরো ভিত এই "সসীম ঘড়ি"।
আর এটা **033 — Fermat Little Theorem**-এর যমজ: Fermat বলে prime mod-এ `a^(p−1) ≡ 1` — মানে cycle ঠিক (p−1) (বা তার ভাগ)। 036 সেই ধারণাটাই last-digit-এর সহজ, হাতে-গোনা রূপে দেখায়। আর 029-এর fast power হলো এর "যেকোনো mod"-এর general সমাধান; cyclicity হলো বিশেষ অন্তর্দৃষ্টি।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **cyclicity of powers (modular periodicity)**। mod m-এর ঘড়িতে ঘর মোটে m টা। তাই `b, b², b³, ...`-এর remainder-গুলো 0..m−1-এর মধ্যেই ঘোরে — pigeonhole-এ একসময় আগের কোনো remainder ফিরবেই, আর ফিরলেই পুরো ধারা সেখান থেকে চক্রাকারে পুনরাবৃত্তি।
তাই যদি cycle-এর দৈর্ঘ্য `L` হয়:
`b^e % m = b^((e−1) % L + 1) % m` (1-indexed চক্রে)
last digit-এ এটা mod 10; cycle সাধারণত 1, 2, বা 4 দৈর্ঘ্যের হয়। এটাই Fermat (033)-এর `a^(p−1) ≡ 1`-এর সাধারণ রূপ: prime mod-এ cycle (p−1)-কে ভাগ করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল: সরাসরি power বের করে last digit (Python big int-এ সম্ভব), অথবা প্রতি step-এ mod 10 নিয়ে e বার গুণ।
```python
def last_digit_brute(b, e):
if e == 0:
return 1
d = 1
for _ in range(e):
d = d * b % 10 # e বার গুণ, প্রতি step mod 10
return d
```
ঠিক উত্তর দেয়। সমস্যা একটাই — loop চলে `e` বার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে `e` বার। `e = 10^18` হলে কার্যত অসম্ভব। (`pow(b, e, 10)` দিয়েও O(log e)-তে হয়, কিন্তু cyclicity-র অন্তর্দৃষ্টি দেখায় কেন উত্তর এত সহজ — অনেক সময় হাতে-মুখে বের করা যায়।)
```text
e = 10^18 হলে:
brute (O(e)): 10^18 বার গুণ -> অসম্ভব
cyclicity (O(L)): cycle length L (≤4 last digit-এ) বের, তারপর e % L
-> মুঠোয়, এমনকি হাতে-কলমে
```
মূল শিক্ষা: পুরো power বের না করে, ছোট চক্রটা ধরো — তারপর `e % L` দিয়ে সরাসরি ঘর।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
চক্র বের করো (যতক্ষণ না remainder পুনরাবৃত্তি), তারপর `e`-কে cycle-দৈর্ঘ্য দিয়ে mod করে ঘর বেছে নাও:
```python
def last_digit(b, e):
if e == 0:
return 1
cycle = []
d = b % 10
while d not in cycle: # চক্র বানাই যতক্ষণ নতুন
cycle.append(d)
d = d * b % 10
r = e % len(cycle)
return cycle[r - 1] # r=0 হলে cycle[-1] = শেষ ঘর (ঠিক কাজ করে)
```
`cycle[r - 1]`-এর সৌন্দর্য: `r = 0` হলে Python-এ `cycle[-1]` = শেষ ঘর — remainder-0-এর edge case আপনিই সামলে যায়।
general mod-এ (last digit না, যেকোনো m) সরাসরি fast power সবচেয়ে নিরাপদ: `pow(b, e, m)` (029)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **power-এর remainder সসীম ঘড়িতে ঘোরে, তাই একসময় পুনরাবৃত্তি করবেই — চক্রটা ধরো, তারপর exponent-কে চক্র-দৈর্ঘ্য দিয়ে mod করো।** বিশাল exponent তখন ছোট চক্রের একটা ঘরে নেমে আসে।
দুটো সতর্কতা-tweak:
- **remainder 0 = শেষ ঘর**, প্রথম ঘর নয়। `cycle[r-1]` দিয়ে এটা সহজে সামলাও (r=0 → cycle[-1])।
- exponent-কে mod করো, **base-কে নয়**। `7^222`-এ 222 % 4, কখনো 7 % 4 নয়।
### ছবিতে বোঝা {#5-visual-explanation}
`7`-এর power-এর last digit চক্র:
```text
7¹ 7² 7³ 7⁴ 7⁵ 7⁶ 7⁷ 7⁸ ...
7 49 343 2401 ...
last digit: 7, 9, 3, 1, 7, 9, 3, 1, ...
└────────────┘ └────────────┘
চক্র (length 4) আবার একই চক্র
7^222-এর last digit: 222 % 4 = 2 -> চক্রের 2 নম্বর ঘর -> 9
```
remainder 0 হলে সাবধান — চক্রের **শেষ** ঘর:
```text
7^8-এর last digit: 8 % 4 = 0 -> remainder 0 মানে চক্রের শেষ ঘর (4র্থ) -> 1
(0 কে "ঘর 0" ভেবো না; এটা পুরো এক চক্র শেষ — শেষ ঘরে দাঁড়ানো)
ভাষায়: index = (e-1) % 4, তারপর cycle[index]; e=8 -> (7)%4=3 -> cycle[3]=1 ✓
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`last_digit(7, 222)`:
```text
e = 222 ≠ 0, তাই চক্র বানাই (d = 7 % 10 = 7 থেকে শুরু):
```
| step | d (আগে) | cycle এ আছে? | cycle append | পরের d = d×7 % 10 |
| --- | --- | --- | --- | --- |
| 1 | 7 | না | [7] | 49 % 10 = 9 |
| 2 | 9 | না | [7, 9] | 63 % 10 = 3 |
| 3 | 3 | না | [7, 9, 3] | 21 % 10 = 1 |
| 4 | 1 | না | [7, 9, 3, 1] | 7 % 10 = 7 |
| 5 | 7 | হ্যাঁ (থামল) | — | — |
cycle = [7, 9, 3, 1], length 4। এবার:
```text
r = 222 % 4 = 2 -> cycle[r-1] = cycle[1] = 9
```
উত্তর **9**। Check: `pow(7, 222, 10) = 9` ✓ (Python-এ মিলিয়ে দেখো)।
আর remainder-0 কেস `last_digit(7, 8)`: `8 % 4 = 0` → `cycle[-1] = 1`। Check: `pow(7, 8, 10) = 1` ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def last_digit(b, e):
"""b^e-এর শেষ অঙ্ক (b^e % 10), cyclicity দিয়ে।"""
if e == 0:
return 1 # b^0 = 1 (b ≠ 0 ধরে; 0^0 আলাদা গল্প)
cycle = []
d = b % 10
while d not in cycle:
cycle.append(d)
d = d * b % 10
r = e % len(cycle)
return cycle[r - 1] # r=0 -> cycle[-1] = শেষ ঘর
def power_mod_general(b, e, m):
"""যেকোনো mod-এ b^e % m — fast power, সবচেয়ে নিরাপদ general পথ।"""
return pow(b, e, m)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert last_digit(7, 222) == 9
assert last_digit(2, 10) == 4
assert last_digit(3, 4) == 1 # remainder 0 -> শেষ ঘর
assert last_digit(5, 100) == 5 # cycle length 1
assert last_digit(6, 7) == 6
assert last_digit(1, 999) == 1
assert last_digit(7, 0) == 1 # b^0 = 1
# মূল যাচাই: Python-এর pow(b, e, 10) এর সাথে মিলিয়ে দেখা
for b in range(2, 30):
for e in range(1, 60):
assert last_digit(b, e) == pow(b, e, 10)
# বিশাল exponent-এও cyclicity ঠিক:
assert last_digit(7, 10**18 + 222) == pow(7, 10**18 + 222, 10)
assert last_digit(2, 10**15) == pow(2, 10**15, 10)
# general mod fast power মিল:
assert power_mod_general(3, 100, 97) == pow(3, 100, 97)
print(last_digit(7, 222)) # 9
print(last_digit(3, 4)) # 1
print(last_digit(2, 10**18)) # বিশাল exponent, ঝটপট
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if e == 0:
return 1
cycle = []
d = b % 10
while d not in cycle:
cycle.append(d)
d = d * b % 10
```
`e = 0` হলে `b^0 = 1`। নাহলে চক্র বানাই: `d` শুরু `b`-এর last digit; যতক্ষণ `d` নতুন (cycle-এ নেই) ততক্ষণ যোগ করি আর পরের power-এর last digit বের করি (`d * b % 10`)। যখন পুরনো d ফিরে আসে — চক্র সম্পূর্ণ, loop থামে।
```text
r = e % len(cycle)
return cycle[r - 1]
```
exponent-কে cycle-দৈর্ঘ্য দিয়ে mod করি — কোন ঘরে পড়ব। `cycle[r-1]` কারণ চক্র 1-indexed অর্থে (1ম power = cycle[0]); আর `r = 0` হলে `cycle[-1]` = শেষ ঘর, যা remainder-0-এর সঠিক উত্তর।
```text
for b in range(2, 30):
for e in range(1, 60):
assert last_digit(b, e) == pow(b, e, 10)
```
এই double loop বহু base আর exponent-এ Python-এর সত্যিকার `pow(b, e, 10)`-এর সাথে মিলিয়ে দেখছে — এটাই সবচেয়ে শক্ত যাচাই। বিশাল exponent (10^18+222)-এও মেলানো হয়েছে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
9
1
... (একটা অঙ্ক, 2^(10^18)-এর শেষ অঙ্ক = 6)
সব test pass!
```
প্রথম লাইন `last_digit(7, 222)` → 9 (চক্রের ঘর 2)। দ্বিতীয় `last_digit(3, 4)` → 1 (remainder 0, শেষ ঘর)। তৃতীয় `last_digit(2, 10**18)` → 6 (2-এর চক্র [2,4,8,6], 10^18 % 4 = 0 → শেষ ঘর 6)। আগের সব `assert` (`pow`-এর সাথে বিশাল exponent সহ মিল) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(L)** চক্র বানাতে, যেখানে `L` = cycle length (last digit-এ সর্বোচ্চ 4)। তারপর `e % L` আর একটা lookup — O(1)। মোট কার্যত O(1) last digit-এর জন্য। `pow(b, e, m)` general পথ O(log e)। brute O(e)-এর তুলনায় বিশাল।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(L)** — শুধু cycle list (last digit-এ ≤4 element)। কার্যত O(1)। `pow` পথে O(1)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **remainder 0 কে প্রথম ঘর ভাবা** — `e % L == 0` মানে চক্রের **শেষ** ঘর, প্রথম নয়। `cycle[r-1]` (r=0 → cycle[-1]) দিয়ে সামলাও; নাহলে এক ঘর ভুল।
- **base-কে mod করা** — exponent-কে cycle-দৈর্ঘ্য দিয়ে mod করো (`222 % 4`), base-কে নয় (`7 % 4` ভুল)।
- **cycle length অনুমান করা** — সব base-এ cycle 4 নয়; 5,6,0,1-এর cycle 1, কারও 2। সবসময় বের করে নাও, ধরে নিও না।
- **`b^0` ভুলে যাওয়া** — `e = 0` হলে উত্তর 1; আলাদা handle না করলে cycle/index ভুল।
- **general mod-এ last-digit cycle ব্যবহার** — mod 10 ছাড়া অন্য m-এ cycle ভিন্ন; general হলে fast power (`pow(b, e, m)`) নিরাপদ।
- **0 বা negative base** — `0^e = 0` (e>0); negative base-এ last digit-এর ধারণা সাবধানে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **033 (Fermat Little Theorem)** (