028 — Modular Multiplication¶
027-এ দেখেছ যোগে প্রতি step-এ mod নিরাপদ। গুণেও ঠিক একই জাদু চলে — আর গুণে এই অভ্যাসটা আরও জরুরি, কারণ গুণফল যোগের চেয়ে অনেক দ্রুত বিশাল হয়ে যায়। এই গুণের নিয়মটাই fast power, inverse, nCr — সব কিছুর engine।
Source¶
- Original source: Classic exercise (modular arithmetic-এর গুণের নিয়ম)
- Platform: Classic exercise — সব CP intro আর number theory বই-তে থাকে
- Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
- Difficulty: Easy
- Pattern: (a*b)%m (modular multiplication)
- Basic idea inherited from: 027 — Modular Addition (প্রতি step-এ mod নেওয়ার নিয়ম)
1. Problem in simple words¶
দুটো (বা অনেকগুলো) integer আর একটা m দেওয়া। বলতে হবে তাদের গুণফল mod m — মানে (a * b) % m।
সমস্যাটা যোগের চেয়ে তীব্র: দুটো বড় সংখ্যার গুণফল প্রকাণ্ড হয় (10⁹ × 10⁹ = 10¹⁸)। তাই আমরা চাই — পুরো গুণফল না বানিয়ে, প্রতি step-এ m-এর ঘড়িতে নামিয়ে কাজ করতে।
অনেকগুলো সংখ্যার গুণফল (যেমন factorial) হলে এই অভ্যাস ছাড়া উপায় নেই।
2. What is the math idea?¶
মূল idea — modular multiplication rule:
(a × b) % m = ((a % m) × (b % m)) % m
গুণের আগে দুজনকে আলাদা করে ঘড়ির ঘরে নামিয়ে নিলেও শেষ উত্তর একই।
কেন? a = q₁m + r₁, b = q₂m + r₂ লিখলে:
a × b = q₁q₂m² + q₁m·r₂ + r₁·q₂m + r₁r₂
প্রথম তিনটে term-এ m আছে — ঘড়িতে পুরো পুরো চক্কর, কাঁটার অবস্থানে প্রভাব নেই। কাঁটা কোথায় থামবে তা ঠিক করে শুধু শেষ term r₁ × r₂। তাই (a×b) % m = (r₁ × r₂) % m।
3. Which basic idea does this inherit from?¶
সরাসরি 027 — Modular Addition থেকে। 027-এ শিখেছ যোগে প্রতি step-এ mod নিরাপদ; 028 ঠিক একই দর্শন গুণে প্রয়োগ করে।
আসলে গুণ মানে বারবার যোগ — a × b মানে a-কে b বার যোগ। যোগে যদি প্রতি step-এ mod চলে, গুণেও চলবে, এটাই স্বাভাবিক। 027-এর "প্রতি step-এ ছোট করে নাও" idea-টাই এখানে গুণফলে বিস্তৃত।
আর শিকড়ে — 026 (remainder) → 027 (যোগ) → 028 (গুণ); ধাপে ধাপে একই ঘড়ির উপর নতুন operation।
4. Real-life analogy¶
আবার 12 ঘণ্টার ঘড়ি। ধরো প্রতি বৈঠক 7 ঘণ্টা, এমন 5টা বৈঠক পরপর — মোট 7 × 5 = 35 ঘণ্টা পরে কাঁটা কোথায়? 35 % 12 = 11।
এখন চালাকি: 7 তো ঘড়িতে 7-ই। কিন্তু যদি প্রতি বৈঠক 100 ঘণ্টা হতো? 100 % 12 = 4 — মানে প্রতি বৈঠক ঘড়ির হিসাবে "4 ঘণ্টার সমান"। 5টা বৈঠক = (4 × 5) % 12 = 20 % 12 = 8; আর সরাসরি 500 % 12 = 8। মিলে গেল! বড় 500 না বানিয়েও উত্তর পেলাম। এই "আগে ছোট করো, তারপর গুণো" — এটাই modular multiplication।
5. Visual explanation¶
m = 12 ধরে, গুণের আগে-পরে mod একই ফল দেয়:
(100 × 5) % 12 দুই রাস্তায়:
রাস্তা A (সরাসরি): 100 × 5 = 500 -> 500 % 12 = 8
রাস্তা B (প্রতি step):
100 % 12 = 4
5 % 12 = 5
(4 × 5) % 12 = 20 % 12 = 8
^ একই! কিন্তু সংখ্যা কখনো 20 ছাড়াল না
অনেকগুলো গুণে (factorial-এর মতো) সংখ্যা ছোট থাকে দেখো — 5! % 7:
result শুরুতে 1, প্রতি step-এ × i তারপর % 7:
1 ──×2──> 2 %7=2 ──×3──> 6 %7=6 ──×4──> 24 %7=3 ──×5──> 15 %7=1
^
result কখনো 6×5=30-এর বেশি গেল না, যদিও 5! = 120
6. Example input and output¶
a b m -> (a*b)%m ব্যাখ্যা
-----------------------------------------------------
7 5 12 -> 11 35 % 12 = 11
100 5 12 -> 8 500 % 12 = 8
6 4 7 -> 3 24 % 7 = 3
10**9 10**9 7 -> 1 10^18 % 7 (নিজে মিলাও)
list-এর গুণফল (mod):
nums m -> product % m
-----------------------------------------
[2,3,4,5] 7 -> 3 120 % 7 = 3 (= 5! % 7)
[10**9]*5 13 -> ... প্রতি step-এ mod
খেয়াল করো 10⁹ × 10⁹ = 10¹⁸ — C++-এ এটা signed 64-bit-এর কিনারায়; বড় হলে overflow।
7. Brute force thinking¶
সবচেয়ে সরল: পুরো গুণফল বানিয়ে শেষে একবার mod।
def mul_mod_brute(a, b, m):
return (a * b) % m # আগে পুরো গুণফল, তারপর mod
def product_mod_brute(nums, m):
p = 1
for x in nums:
p *= x # পুরো গুণফল জমাতে থাকি
return p % m # শেষে একবার mod
Python-এ ঠিক উত্তর দেয়। কিন্তু এখানেই বিপদের বীজ — গুণফল লাফিয়ে লাফিয়ে বাড়ে।
8. Why brute force may be slow¶
গুণে সংখ্যা যোগের চেয়ে অনেক দ্রুত বাড়ে:
- C++/Java-তে overflow:
10⁹ × 10⁹ = 10¹⁸64-bit-এর সীমার কাছে; আর কয়েকটা গুণেই সীমা ছাড়িয়ে wrap → garbage। - Python-এ slowness:
product_mod_brute-এ মাঝের গুণফল লক্ষ লক্ষ digit-এর হয়ে যায় (যেমন 100! বা বড়), প্রতিটা গুণ ক্রমশ ধীর; পুরো হিসাব সেকেন্ড-মিনিটে গড়ায়।
factorial(100000) % MOD:
brute: মাঝের গুণফল ~456574 digit, প্রতিটা গুণ ভয়াবহ ধীর
smart: প্রতি গুণের পরেই % MOD -> সংখ্যা কখনো MOD² ছাড়ায় না, ঝটপট
মূল শিক্ষা: গুণফলকে বড় হওয়ার সুযোগই দিও না।
9. Better thinking¶
modular multiplication rule কাজে লাগাই — প্রতি গুণের পরেই mod:
list-এর জন্য প্রতি step-এ mod নিয়ে জমাও:
def product_mod(nums, m):
p = 1
for x in nums:
p = p * x % m # প্রতি গুণের পরেই ঘড়িতে নামাও
return p
এখন মাঝের p কখনো m²-এর বেশি বড় হয় না — ছোট, দ্রুত, overflow-মুক্ত। factorial-mod এই কাঠামোতেই লেখা হয়।
10. Thinking tweak¶
আসল "আহা!": গুণফলকে বড় হতে দিও না — প্রতিটা গুণের পরপরই % m নাও। গুণে বৃদ্ধি যোগের চেয়ে দ্রুত, তাই এই অভ্যাসটা আরও জরুরি।
আরেকটা সূক্ষ্ম tweak: p = p * x % m-এ Python operator precedence-এ * আগে চলে, তারপর % — মানে এটা (p * x) % m, ঠিক যা চাই। কিন্তু পরিষ্কার থাকতে চাইলে bracket দিয়ে p = (p * x) % m লেখো; দুটো একই।
11. Step-by-step dry run¶
nums = [2, 3, 4, 5], m = 7 (মানে 4! × ... আসলে 2×3×4×5 = 120 = 5!) — প্রতি step-এ mod:
| step | x | p (আগে) | p * x | (p * x) % 7 |
|---|---|---|---|---|
| শুরু | — | 1 | — | 1 |
| 1 | 2 | 1 | 2 | 2 % 7 = 2 |
| 2 | 3 | 2 | 6 | 6 % 7 = 6 |
| 3 | 4 | 6 | 24 | 24 % 7 = 3 |
| 4 | 5 | 3 | 15 | 15 % 7 = 1 |
উত্তর 1। Check সরাসরি: 2×3×4×5 = 120, 120 % 7 = 1 ✓ (120 = 7×17 + 1)। লক্ষ করো p কখনো 24-এর বেশি গেল না, যদিও পুরো গুণফল 120।
single গুণ dry run (100 × 5) % 12:
12. Python solution¶
def mul_mod(a, b, m):
"""(a * b) % m — প্রতি অপারেন্ড আগে ঘড়িতে নামিয়ে।"""
return ((a % m) * (b % m)) % m
def product_mod(nums, m):
"""list-এর সব সংখ্যার গুণফল mod m — প্রতি step-এ mod।"""
p = 1
for x in nums:
p = (p * x) % m
return p
def factorial_mod(n, m):
"""n! % m — modular multiplication-এর সরাসরি প্রয়োগ।"""
p = 1
for i in range(2, n + 1):
p = (p * i) % m
return p
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert mul_mod(7, 5, 12) == 11 # 35 % 12
assert mul_mod(100, 5, 12) == 8 # 500 % 12
assert mul_mod(6, 4, 7) == 3 # 24 % 7
# brute (সরাসরি গুণ) এর সাথে মিলিয়ে দেখা:
assert mul_mod(10**9, 10**9, 7) == (10**9 * 10**9) % 7
assert product_mod([2, 3, 4, 5], 7) == 1 # 120 % 7
assert product_mod([2, 3, 4, 5], 7) == (2 * 3 * 4 * 5) % 7
assert factorial_mod(5, 7) == 1 # 120 % 7 = 1
import math
assert factorial_mod(10, 1000000007) == math.factorial(10) % 1000000007
assert factorial_mod(20, 13) == math.factorial(20) % 13
print(mul_mod(7, 5, 12)) # 11
print(product_mod([2, 3, 4, 5], 7)) # 1
print(factorial_mod(5, 7)) # 1
print("সব test pass!")
13. Line-by-line explanation¶
দুজনকে আগে আলাদা করে ঘড়িতে নামাই, গুণ করি, আবার % m। তাই মাঝের গুণফল কখনো m²-এর বেশি বড় হয় না — overflow-নিরাপদ।
p শুরু 1 (গুণের identity)। প্রতিটা সংখ্যা গুণ করি, কিন্তু প্রতি step-এই % m। তাই p ছোট থাকে।
2 থেকে n পর্যন্ত গুণ — এটাই n! কিন্তু প্রতি step-এ mod নেওয়া। nCr mod p-এর factorial precompute এই কাঠামোরই বড় রূপ।
assert ... == math.factorial(...) % ... লাইনগুলো Python-এর সত্যিকার factorial-এর সাথে মিলিয়ে দেখছে — এটাই নিশ্চিত করে আমাদের mod-হিসাবে ভুল নেই। সব ঠিক থাকলে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন mul_mod(7, 5, 12) → 11 (35 mod 12)। দ্বিতীয় product_mod([2,3,4,5], 7) → 1 (120 mod 7)। তৃতীয় factorial_mod(5, 7) → 1 (5! = 120, mod 7 = 1)। আগের সব assert (math.factorial-এর সাথে মিল সহ) চুপচাপ pass — তারপর সব test pass!।
15. Time complexity¶
mul_mod: O(1) — গুটিকয় mod আর একটা গুণ।product_mod,factorial_mod: O(n) —nটা সংখ্যার উপর একবার করে loop, প্রতিবার O(1) কাজ।
brute force-এর সাথে Big-O একই, কিন্তু এখানে মাঝের সংখ্যা ছোট থাকায় প্রতিটা গুণ সস্তা (বড় সংখ্যার গুণ Python-এ ধীর) আর C++-এ overflow নেই।
16. Space complexity¶
O(1) — input ছাড়া শুধু একটা p variable। বাড়তি list/array লাগছে না।
17. Common mistakes¶
- শেষে একবারে mod নেওয়া —
(a * b * c) % mPython-এ ঠিক, কিন্তু মাঝের সংখ্যা বিশাল হয়ে slow; C++/Java-তে overflow-এ ভুল উত্তর। অভ্যাস: প্রতি গুণের পরেই% m। 10⁹ × 10⁹C++-এ সরাসরি গুণ — 10¹⁸ signed 64-bit-এর কিনারায়; কয়েক গুণেই overflow। আগে mod নিয়ে তারপর গুণ নিরাপদ।pশুরুতে 0 দেওয়া — গুণে identity হলো 1, 0 নয়;p = 0দিলে সব গুণফল 0।- mod 1 ভুলে যাওয়া — সব কিছু mod 1 = 0; factorial-ও 0।
- operand আগে mod না নেওয়া —
aনিজেই m-এর চেয়ে বড় হলে(a % m)আগে নিলে গুণফল আরও ছোট থাকে; নাহলে অযথা বড় সংখ্যার গুণ।
18. Harder problems that inherit this idea¶
- CSES — Exponentiation (https://cses.fi/problemset/task/1095) — fast power-এর প্রতিটা square আর multiply আসলে এই modular multiplication; না জানলে সেটা অচল।
- 029 (Modular Exponentiation) — পরের সরাসরি ধাপ: গুণকে বারবার square করে power।
- 034 (nCr mod Prime) — factorial precompute (এই
factorial_mod-এর বড় রূপ) + inverse — সবটাই এই গুণের নিয়মের উপর দাঁড়ানো।
19. Pattern learned¶
Mod at every step (multiplication) — (a × b) % m = ((a%m) × (b%m)) % m; list/factorial-এ প্রতি গুণের পরেই % m। গুণফলকে কখনো বড় হতে দিও না; identity হলো 1। এটাই fast power, factorial-mod, hashing — সবার ভিত।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "গুণে প্রতি step-এ % m নাও — গুণফল যোগের চেয়ে দ্রুত বাড়ে, তাই আরও জরুরি। p শুরু 1, প্রতি গুণের পরেই mod। factorial-mod আর fast power-এর গোড়া এটাই।"
পরের ধাপ → 029 — Modular Exponentiation (গুণকে square করে power বানানো)। সম্পর্কিত → 027 — Modular Addition, 038 — Hashing with Mod।
ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।