Greedy Algorithm ও Number Theory বাংলায় | পর্ব ৪৩

Q: একটি সমস্যায় greedy কাজ করবে কি না, আগে থেকে বুঝবেন কীভাবে?

কোনো জাদুর বোতাম নেই, কিন্তু কয়েকটি নির্ভরযোগ্য সংকেত আছে। পাঠ্যবইয়ে এগুলোকে দুটি নামে ডাকা হয়: Greedy-choice property: প্রথম ধাপের greedy পছন্দটি কোনো না কোনো সেরা সমাধানের অংশ। Activity selection-এ exchange argument দিয়ে আমরা ঠিক এটিই দেখিয়েছি। Optimal substructure: প্রথম পছন্দের পরে যে ছোট সমস্যাটি থাকে, তার সেরা সমাধান আর প্রথম পছন্দ মিলে পুরো সমস্যার সেরা সমাধান হয়। এই গুণটি DP-তেও লাগে — পার্থক্য হলো DP প্রতিটি ধাপে সব পছন্দ যাচাই করে, greedy একটিই নেয়। গণিতবিদেরা আরও গভীরে গিয়ে একটি কাঠামো খুঁজে পেয়েছেন, যার নাম matroid . মোটামুটি বললে, যে সমস্যার “বৈধ বাছাই”-গুলো কিছু নির্দিষ্ট নিয়ম মানে (যেমন বৈধ বাছাইয়ের যেকোনো অংশও বৈধ, আর ছোট বৈধ বাছাইকে বড়টি থেকে একটি জিনিস এনে বাড়ানো যায়), সেখানে ওজন যা-ই হোক, “সবচেয়ে ভারী আগে” greedy সবসময় সেরা। Kruskal-এর অ্যালগরিদম ঠিক এই কারণেই সঠিক।

Q: কনটেস্টে 1,000,000,007 আর 998,244,353 — এই দুটি অদ্ভুত সংখ্যাই কেন বারবার আসে?

কনটেস্টের আয়োজকেরা চান উত্তরটি বিশাল হলেও যাচাই করা সহজ হোক। “উত্তরের ভাগশেষ দিন” বললে প্রতিযোগীর কাজ হয় প্রতিটি ধাপে ভাগশেষ রাখা, আর বিচারকের কাজ একটিমাত্র সংখ্যা মেলানো। কিন্তু m যেকোনো সংখ্যা হলে চলে না — কয়েকটি শর্ত পূরণ করতে হয়। Prime হতে হবে: তাহলে শূন্য ছাড়া প্রতিটি সংখ্যার inverse আছে, আর ভাগ লাগে এমন সূত্র (যেমন nCr = n! / (r! (n−r)!)) Fermat দিয়ে হিসাব করা যায়। m যৌগিক হলে কিছু সংখ্যার inverse থাকে না, আর সূত্র ভেঙে পড়ে। আকার ঠিক হতে হবে: 10 9 + 7 এত বড় যে এলোমেলো ভুল উত্তর কাকতালীয়ভাবে মিলে যাওয়ার সম্ভাবনা নগণ্য, আবার এত ছোট যে দুটি ভাগশেষের যোগফল 32-bit int -এ আর গুণফল 64-bit-এ আঁটে। 10 9 + 7 মনে রাখাও সহজ — ১-এর পরে আটটি শূন্য, তারপর ৭. 998244353 কেন? এটিও prime, আর এর একটি বিশেষ গঠন আছে: 998244353 = 119 × 2 23 + 1. অর্থাৎ (m − 1)-এর ভেতরে ২-এর একটি বড় ঘাত লুকিয়ে আছে।

Q: Greedy কি শুধু ক্লাসরুমের জিনিস, নাকি বাস্তব সিস্টেমেও চলে?

Greedy আপনার চারপাশের সফটওয়্যারে সবখানে — কখনো প্রমাণিত সেরা হিসেবে, কখনো “যথেষ্ট ভালো আর দ্রুত” আন্দাজ হিসেবে। ফাইল সংকোচন: Huffman coding আজও ZIP, gzip ও PNG-র DEFLATE পদ্ধতিতে আর JPEG-এ ব্যবহার হয়। আপনি প্রতিদিন যত ছবি দেখেন, তার অনেকগুলোর ভেতরে Huffman-এর greedy গাছ আছে। ইন্টারনেট রাউটিং: বড় নেটওয়ার্কের ভেতরে পথ খোঁজার OSPF প্রোটোকল প্রতিটি রাউটারে Dijkstra-র greedy অ্যালগরিদম চালায়। ম্যাপ অ্যাপের পথ খোঁজাও এর বংশধর। নেটওয়ার্ক নকশা: গ্রামে বিদ্যুতের লাইন বা অফিসে তার সবচেয়ে কম খরচে জোড়ার প্রশ্নে Kruskal বা Prim-এর greedy অ্যালগরিদম প্রমাণিত সেরা উত্তর দেয়। কাজের সময়সূচি: অপারেটিং সিস্টেম আর ক্লাউড সার্ভারে “সবচেয়ে ছোট কাজ আগে” (Shortest Job First) গড় অপেক্ষার সময় কমায় — যদিও বাস্তবে কাজের দৈর্ঘ্য আগে জানা থাকে না, তাই আন্দাজ করতে হয়। Cache-এর গল্পটি সবচেয়ে শিক্ষণীয়।

এক নজরে · TL;DR

Greedy মানে এখনই সেরাটা নেওয়া, পেছনে না তাকানো। একটি রুমে সবচেয়ে বেশি অনুষ্ঠান রাখতে “যেটা আগে শেষ হয়, সেটা আগে” — এই নিয়ম সবসময় সেরা উত্তর দেয়।
Greedy ঠকাতেও পারে: টাকার নোটে বড় নোট আগে দিলে সবচেয়ে কম নোট লাগে, কিন্তু কয়েন {1, 3, 4} দিয়ে 6 বানাতে greedy দেয় ৩টি, অথচ ২টিই যথেষ্ট। তখন লাগে পর্ব ৪২-এর dynamic programming.
GCD আর prime খোঁজার প্রাচীন কৌশল আজও সেরা: ইউক্লিডের ভাগশেষ-কৌশল আর Eratosthenes-এর ছাঁকনি — দুটোই দুই হাজার বছরেরও বেশি পুরোনো, আর দুটোই আশ্চর্য দ্রুত।
Modular arithmetic হলো ঘড়ির অঙ্ক। যোগ ও গুণের প্রতিটি ধাপে % m নিলে সংখ্যা ছোট থাকে। C-তে ঋণাত্মক সংখ্যার % ঋণাত্মক আসে — ঠিক করার সূত্র ((x % m) + m) % m.
AI-এর যুগে: AI-এর greedy “সমাধান” প্রায়ই ছোট উদাহরণে ঠিক, বড় ক্ষেত্রে ভুল। সবসময় ছোট ইনপুটে brute force-এর সাথে মিলিয়ে দেখুন, আর গুণের আগে long long আছে কি না দেখুন।

এই পর্বে যা শিখবেন

Greedy চিন্তা কী, কখন এটি নিখুঁত উত্তর দেয় আর কখন দেয় না — এবং কেন
ইউক্লিডের পদ্ধতিতে GCD, আর overflow ছাড়া LCM বের করার নিরাপদ ক্রম
Sieve of Eratosthenes দিয়ে একসাথে লাখো prime খুঁজে বের করা
Modular arithmetic-এর নিয়ম, কনটেস্টে 1,000,000,007 কেন আসে, আর দ্রুত ঘাত (fast power)
এই গণিত কীভাবে RSA, অনলাইন ব্যাংকিং আর কার্ড নম্বর যাচাইয়ের পেছনে কাজ করে

১ · Greedy — এই মুহূর্তের সেরা পছন্দ

চায়ের দোকানের সামনে দাঁড়িয়ে আপনি ১০০ টাকার নোট দিলেন, চা ১৫ টাকা। দোকানদার ৮৫ টাকা ফেরত দেবেন। তিনি কী করেন? না ভেবেই প্রথমে ৫০-এর নোট, তারপর ২০, তারপর ১০, শেষে ৫ — মোট ৪টি নোট। প্রতিবার তিনি এমন সবচেয়ে বড় নোটটি নেন যেটি বাকি টাকার চেয়ে বড় নয়।

এই চিন্তার ধরনটির নাম greedy algorithm (বাংলায় “লোভী” পদ্ধতি)। প্রতিটি ধাপে যেটা এখন সবচেয়ে ভালো দেখায়, সেটাই নিয়ে নেওয়া — আর একবার নেওয়া সিদ্ধান্ত কখনো বদলানো হয় না। সব পথ ঘুরে দেখতে হয় না বলে কাজ খুব দ্রুত হয়।

মূল ধারণা

Greedy দুটি প্রশ্নের উত্তর চায়: (১) “এখন সেরা” মানে কী? — কোন মাপকাঠিতে বাছাই হবে, যেমন সবচেয়ে বড় নোট, সবচেয়ে আগে শেষ হওয়া কাজ। (২) এই ছোট ছোট সেরা পছন্দ মিলে কি পুরো সমস্যার সেরা উত্তর হয়? প্রথম প্রশ্নের উত্তর দেওয়া সহজ। দ্বিতীয়টি প্রমাণ করাই আসল কাজ — আর অনেক সময় উত্তরটি “না”।

আগের পর্বে আমরা dynamic programming দেখেছি — সেখানে প্রতিটি ছোট সমস্যার সব সম্ভাবনা হিসাব করে টেবিলে রাখা হয়, তারপর সেরাটা বাছা হয়। Greedy তার ঠিক উল্টো: একটিমাত্র পছন্দ, কোনো টেবিল নেই। কাজ করলে এটি DP-র চেয়ে অনেক দ্রুত ও সহজ; কাজ না করলে দ্রুত একটি ভুল উত্তর দেয় — কোনো সতর্কবার্তা ছাড়াই।

২ · একটি সেমিনার রুম, অনেক অনুষ্ঠান

আপনার কলেজে একটিই সেমিনার রুম। শনিবারের জন্য ছয়টি ক্লাব রুম চেয়েছে, প্রত্যেকের নিজস্ব শুরু ও শেষের সময় আছে। একই সময়ে রুমে একটির বেশি অনুষ্ঠান চলতে পারবে না। লক্ষ্য: সবচেয়ে বেশি সংখ্যক অনুষ্ঠান রাখা। (ধরে নিচ্ছি একটি অনুষ্ঠান ১০টায় শেষ হলে পরেরটি ১০টাতেই শুরু করা যায়।) এই সমস্যাটির নাম activity selection — ঢাকার একটি ভাড়া-বাসে দিনে সবচেয়ে বেশি ট্রিপ বুক করা, বা একজন ডাক্তারের দিনে সবচেয়ে বেশি রোগী দেখার সময় ঠিক করাও একই সমস্যা।

কোন নিয়মে বাছবেন? তিনটি স্বাভাবিক চিন্তা মাথায় আসে:

নিয়ম	শুনতে কেমন	কোথায় ভাঙে
যেটা সবচেয়ে আগে শুরু হয়	“আগে এলে আগে পাবে” — ন্যায্য মনে হয়	সকাল ৭টা থেকে দুপুর ২টা পর্যন্ত একটি বিজ্ঞান মেলা পুরো দিনটাই খেয়ে ফেলে
যেটা সবচেয়ে ছোট	“ছোট কাজ কম জায়গা নেয়”	১–৫ আর ৬–১০-এর মাঝখানে ৪–৭ ছোট, কিন্তু দুটোকেই আটকে দেয়: ২টির বদলে ১টি
যেটা সবচেয়ে আগে শেষ হয়	“রুম যত তাড়াতাড়ি খালি, তত ভালো”	কোথাও ভাঙে না — এটিই সঠিক নিয়ম

তৃতীয় নিয়মটি কাজ করে দেখুন। প্রথমে সব অনুষ্ঠান শেষ হওয়ার সময় অনুযায়ী সাজানো হয়েছে। তারপর একে একে দেখা: শুরুর সময় যদি রুম খালি হওয়ার সময়ের সমান বা পরে হয়, তাহলে নেওয়া হবে; না হলে বাদ।

শেষের সময় অনুযায়ী সাজানো ছয়টি অনুরোধ

A · গণিত ক্লাব 8–10
B · বিতর্ক 9–11
C · রোবোটিক্স 10–12
D · ফটোগ্রাফি 11–13
E · বিজ্ঞান মেলা 7–14
F · কুইজ 12–14
রুম খালি হবে
মোট নেওয়া

সাজানো তালিকা। ছয়টি অনুরোধ শেষের সময় অনুযায়ী সাজানো: ১০, ১১, ১২, ১৩, ১৪, ১৪. পর্ব ২৮-এর qsort আর একটি comparator দিয়ে এই সাজানোটা এক লাইনের কাজ। বিজ্ঞান মেলা (E) সবার আগে শুরু হয়, কিন্তু শেষ হয় প্রায় সবার পরে।
A নেওয়া হলো। রুম এখনো পুরো খালি, তাই সবচেয়ে আগে শেষ হওয়া A (৮–১০) নিঃসন্দেহে নেওয়া যায়। এখন রুম খালি হবে ১০টায়। এই একটি সংখ্যাই আমাদের পুরো “স্মৃতি”।
B বাদ। বিতর্ক শুরু ৯টায়, কিন্তু রুম ১০টা পর্যন্ত ব্যস্ত। বাদ।
C নেওয়া হলো। রোবোটিক্স শুরু ঠিক ১০টায় — রুম তখনই খালি হচ্ছে। নেওয়া হলো, এখন রুম খালি হবে ১২টায়।
D বাদ। ফটোগ্রাফি ১১টায় শুরু, রুম তখন রোবোটিক্সের দখলে। বাদ।
E বাদ। বিজ্ঞান মেলা ৭টায় শুরু — অনেক আগেই। “আগে শুরু হলে আগে পাবে” নিয়মে এটিকেই সবার আগে নিতাম, আর সারাদিনে মাত্র ১টি অনুষ্ঠান হতো!
F নেওয়া হলো — শেষ। কুইজ ১২টায় শুরু, রুম ঠিক তখন খালি। মোট ৩টি অনুষ্ঠান: A, C, F (৮–১০, ১০–১২, ১২–১৪). ৮টা থেকে ২টা পর্যন্ত রুম এক মিনিটও ফাঁকা নেই, তাই চতুর্থ কোনো অনুষ্ঠান ঢোকানো অসম্ভব — এটিই সেরা উত্তর। মোট খরচ: সাজাতে O(n log n), তারপর একবার পুরো তালিকা দেখা O(n).

কেন “আগে শেষ” কখনো ঠকায় না — বদলে দেওয়ার যুক্তি

একটি উদাহরণে কাজ করা মানেই সব ক্ষেত্রে কাজ করা নয়। নিশ্চিত হওয়ার যুক্তিটির নাম exchange argument (বদলে দেওয়ার যুক্তি)।

ধরুন কেউ দাবি করলেন, তাঁর কাছে একটি “সেরা” সময়সূচি আছে, যার প্রথম অনুষ্ঠানটি X — আমাদের বাছা A নয়। এখন তাঁর সূচি থেকে X সরিয়ে A বসিয়ে দিন। কী ঘটে? A সব অনুষ্ঠানের মধ্যে সবচেয়ে আগে শেষ হয়, তাই A শেষ হয় X-এর সমান সময়ে বা তার আগে। ফলে X-এর পরে যে অনুষ্ঠানগুলো ছিল, তাদের কারও সাথে A-র সংঘাত হতে পারে না। সূচিটি এখনো বৈধ, আর অনুষ্ঠানের সংখ্যা একই রইল।

ক্রিকেট দলে একজন খেলোয়াড় বদলানোর মতো ভাবুন। যদি নতুনজন পুরোনোজনের চেয়ে কোনো দিক থেকে খারাপ না হন, তাহলে বদলালে দল দুর্বল হয় না। “আগে শেষ হওয়া অনুষ্ঠান” রুমকে সবার আগে ছেড়ে দেয়, তাই যেকোনো সেরা সূচির প্রথম পছন্দকে এটি দিয়ে বদলালে সূচিটি সেরাই থাকে। একই যুক্তি দ্বিতীয়, তৃতীয়… প্রতিটি ধাপে খাটে।

৩ · যখন greedy ঠকায় — টাকার নোট বনাম অদ্ভুত কয়েন

চায়ের দোকানের হিসাবে ফিরে যাই। বাংলাদেশের নোট ও কয়েনের মান ধরা যাক: ১, ২, ৫, ১০, ২০, ৫০, ১০০, ৫০০, ১০০০ (২০০ টাকার নোট যোগ করলেও নিচের কথা বদলায় না)। এই ব্যবস্থায় “সবচেয়ে বড় নোট আগে” নিয়মটি সবসময় সবচেয়ে কম সংখ্যক নোট দেয়। যেমন ১,৮৭৫ টাকা = ১০০০ + ৫০০ + ১০০ + ১০০ + ১০০ + ৫০ + ২০ + ৫ — ৮টি নোট, এর চেয়ে কমে সম্ভব নয়। (আমরা ১ থেকে ৪,০০০ পর্যন্ত প্রতিটি পরিমাণ একটি প্রোগ্রাম দিয়ে DP-র উত্তরের সাথে মিলিয়ে দেখেছি — একটিও অমিল নেই।)

কিন্তু কল্পনা করুন একটি দেশ, যেখানে কয়েন মাত্র তিনটি: ১, ৩ আর ৪. আপনাকে ৬ বানাতে হবে, আর কয়েন লাগবে যত কম সম্ভব — এটিই পর্ব ৪২-এর coin change সমস্যা।

🤑 Greedy-র উত্তর

সবচেয়ে বড় ৪ নিলাম, বাকি ২. এখন ৩ নেওয়া যায় না, তাই ১, আবার ১. মোট ৩টি কয়েন: ৪ + ১ + ১.

দ্রুত, কিন্তু ভুল

✅ সেরা উত্তর

৩ + ৩ = ৬. মাত্র ২টি কয়েন। প্রথম ধাপে “বড়” ৪-কে ছেড়ে দিতে হতো — যা greedy কখনো করে না।

DP খুঁজে পায় (পর্ব ৪২)

এখানেই greedy-র মূল দুর্বলতা। প্রথম পছন্দটি (৪) তখন সেরা দেখালেও পরের ধাপগুলো খারাপ করে দেয়, আর greedy পেছনে ফিরে সংশোধন করে না। একটি counterexample — একটিমাত্র ইনপুট যেখানে নিয়ম ভুল করে — একটি নিয়মকে বাতিল করার জন্য যথেষ্ট।

টাকার নোটে greedy কেন কাজ করে? ১-২-৫ ধাঁচের ব্যবস্থায় বড় নোট এড়িয়ে গিয়ে কখনো লাভ হয় না। বেশিরভাগ মুদ্রাব্যবস্থা ইচ্ছে করেই এভাবে বানানো, যাতে দোকানদার না ভেবেই সঠিক ভাংতি দিতে পারেন। নতুন কোনো কয়েন-ব্যবস্থা পেলে সহজ পরীক্ষা হলো ছোট পরিমাণগুলোতে DP-র সাথে মিলিয়ে দেখা।

কম্পিউটার বিজ্ঞানের কয়েকটি বিখ্যাত অ্যালগরিদম আসলে greedy. ১৯৫২ সালে MIT-র ছাত্র David Huffman একটি কোর্সের টার্ম পেপার হিসেবে বের করেন Huffman coding — যে অক্ষর বেশি আসে তাকে ছোট কোড, যা কম আসে তাকে লম্বা কোড; প্রতি ধাপে সবচেয়ে কম আসা দুটি অক্ষর জোড়া লাগানো হয়। আজও ZIP, gzip, PNG আর JPEG-এর ভেতরে এর ব্যবহার আছে। পর্ব ৩৮-এর Dijkstra-র অ্যালগরিদমও greedy: প্রতিবার সবচেয়ে কাছের অজানা vertex-টি চূড়ান্ত করা। আর নেটওয়ার্কের তার বা রাস্তা সবচেয়ে কম খরচে জোড়ার Kruskal-এর অ্যালগরিদম প্রতিবার সবচেয়ে সস্তা edge-টি নেয়, যদি তাতে চক্র না হয়। তিনটিরই সঠিকতার প্রমাণ আছে।

৪ · প্রোগ্রামারের নাম্বার থিওরি — ভাগ, ভাগশেষ আর prime

Number theory হলো পূর্ণসংখ্যার গণিত — কোন সংখ্যা কাকে ভাগ করে, ভাগশেষ কত, কোন সংখ্যা ভাঙা যায় না। একসময় একে বাস্তবে অকেজো “বিশুদ্ধ” গণিত মনে করা হতো; আজ আপনার ফোনের প্রতিটি নিরাপদ সংযোগ — bKash লগইন থেকে শুরু করে HTTPS ওয়েবসাইট — এই গণিতের ওপর দাঁড়িয়ে আছে।

শুরু করি একদম মৌলিক কথা দিয়ে। Divisibility মানে বিভাজ্যতা: a যদি b-কে নিঃশেষে ভাগ করে, অর্থাৎ b % a == 0, তাহলে বলি a হলো b-এর একটি উৎপাদক (factor) বা ভাজক। C-তে এই প্রশ্নের উত্তর দেয় পর্ব ০৭-এর modulus অপারেটর %.

মূল ধারণা

১-এর চেয়ে বড় যে সংখ্যার উৎপাদক শুধু ১ আর সে নিজে, তা হলো prime number (মৌলিক সংখ্যা): ২, ৩, ৫, ৭, ১১, ১৩… বাকিগুলো composite (যৌগিক): যেমন ১২ = ২ × ২ × ৩. প্রতিটি পূর্ণসংখ্যা prime-গুলোর গুণফল হিসেবে ঠিক একভাবেই লেখা যায় — prime হলো সংখ্যার “পরমাণু”। ১ prime নয়; একে prime ধরলে এই “একভাবেই” কথাটি ভেঙে যেত (১২ = ১ × ২ × ২ × ৩ = ১ × ১ × ২ × ২ × ৩…)।

একটি সংখ্যা prime কি না — √n পর্যন্ত দেখলেই যথেষ্ট

৯১ কি prime? সরল পথ হলো ২ থেকে ৯০ পর্যন্ত প্রতিটি দিয়ে ভাগ করে দেখা। কিন্তু একটু ভাবুন: যদি ৯১ = a × b হয়, তাহলে a আর b দুটোই √৯১ (প্রায় ৯.৫)-এর চেয়ে বড় হতে পারে না — তাহলে গুণফল ৯১ ছাড়িয়ে যেত। অর্থাৎ ছোট উৎপাদকটি অবশ্যই ৯-এর মধ্যে থাকবে। ২, ৩, ৪… ৭-এ গিয়ে মিলে যায়: ৯১ = ৭ × ১৩. Prime নয়।

তাই একটি সংখ্যা n যাচাই করতে লুপ চালাতে হয় শুধু i * i <= n পর্যন্ত। ১০ লাখ যাচাই করতে ১০ লাখ ভাগের বদলে লাগে মাত্র প্রায় ১,০০০টি। sqrt(n)-এর বদলে i * i <= n লিখলে দশমিকের গোলমাল এড়ানো যায়। (খুব বড় n-এ i * i নিজেই overflow করতে পারে, তখন i <= n / i লিখুন।)

৫ · GCD — ইউক্লিডের প্রায় ২,৩০০ বছরের পুরোনো অ্যালগরিদম

দুটি সংখ্যার GCD (গসাগু) হলো সবচেয়ে বড় সংখ্যা, যা দুটোকেই নিঃশেষে ভাগ করে। একটি বাস্তব প্রশ্ন: ২৫২ সেমি লম্বা আর ১০৫ সেমি চওড়া একটি মেঝেতে একই মাপের বর্গাকার টাইলস বসাবেন, কোনো টাইলস কাটা যাবে না। সবচেয়ে বড় টাইলসের বাহু কত? উত্তর gcd(২৫২, ১০৫).

স্কুলে আমরা দুটো সংখ্যাকে prime-এ ভেঙে মিল খুঁজতাম। ছোট সংখ্যায় চলে, কিন্তু ৩০০ অঙ্কের সংখ্যাকে prime-এ ভাঙা কোনো কম্পিউটারের পক্ষেও সম্ভব নয় (এ কথায় আমরা অংশ ৯-এ ফিরব)। অথচ সেই সংখ্যাগুলোর GCD বের করা যায় চোখের পলকে — Euclidean algorithm দিয়ে।

প্রাচীন গ্রিক গণিতবিদ ইউক্লিড খ্রিস্টপূর্ব প্রায় ৩০০ সালে আলেকজান্দ্রিয়ায় তাঁর বিখ্যাত বই Elements লেখেন। এর সপ্তম খণ্ডে এই পদ্ধতির বর্ণনা আছে। পদ্ধতিটি সম্ভবত তাঁর আগেই জানা ছিল; তিনি গুছিয়ে লিখেছিলেন। আজও টিকে থাকা সবচেয়ে পুরোনো অ্যালগরিদমগুলোর এটি একটি।

নিয়মটি এক লাইনের: gcd(a, b) = gcd(b, a % b), আর b শূন্য হলে উত্তর a. কেন সত্য? যে সংখ্যা a আর b দুটোকেই ভাগ করে, সে a থেকে b-এর যেকোনো গুণিতক বাদ দিলে যা থাকে তাকেও ভাগ করে — আর ভাগশেষ a % b ঠিক সেটাই। উল্টো দিকেও একই কথা খাটে। তাই (a, b) আর (b, a % b) জোড়ার সাধারণ উৎপাদকগুলো হুবহু এক, ফলে সবচেয়ে বড়টিও এক। প্রতি ধাপে সংখ্যা ছোট হয়, তাই একসময় শূন্যে পৌঁছাতেই হবে।

1int gcd(int a, int b) {2    while (b != 0) {3        int r = a % b;4        a = b;  b = r;5    }6    return a;7}

ভ্যারিয়েবলের মান

a
b
হিসাব
টাইলসের ভাষায়

শুরু। a = 252, b = 105. b শূন্য নয়, তাই লুপ চলবে। মেঝের ভাষায়: ২৫২ × ১০৫ আয়তক্ষেত্র, এখনো জানি না টাইলস কত বড় হবে।
প্রথম ভাগ। 252 % 105 = 42 (কারণ 252 = 2 × 105 + 42). এবার জোড়াটি হলো (105, 42). মেঝে থেকে ১০৫ × ১০৫ মাপের দুটি বর্গ কেটে নিলে বাকি থাকে ১০৫ × ৪২-এর একটি ফালি। যে টাইলস পুরো মেঝেতে মেলে, সেটি এই ফালিতেও মিলতে বাধ্য।
দ্বিতীয় ভাগ। 105 % 42 = 21. জোড়া (42, 21). দুই ধাপেই ২৫২ থেকে ৪২-এ নেমে এসেছি।
তৃতীয় ভাগ — ভাগশেষ শূন্য। 42 % 21 = 0. জোড়া (21, 0). অর্থাৎ ২১ সেমির বর্গ ৪২ × ২১ ফালিটিকে নিখুঁতভাবে ঢেকে দেয়, তাই পেছনের সব ফালিকেও ঢাকে।
উত্তর ২১. b শূন্য, লুপ শেষ, a = 21 ফেরত। যাচাই: 252 = 2² × 3² × 7, আর 105 = 3 × 5 × 7 — সাধারণ অংশ 3 × 7 = 21. মাত্র তিনটি ভাগে কাজ শেষ। ১৮৪৪ সালে ফরাসি গণিতবিদ Gabriel Lamé প্রমাণ করেন, ধাপের সংখ্যা ছোট সংখ্যাটির অঙ্কসংখ্যার পাঁচ গুণের বেশি কখনো হয় না — তাই ৩০০ অঙ্কের সংখ্যাতেও বড়জোর দেড় হাজারের মতো ধাপ।

LCM — গুণের আগে ভাগ

দুটি সংখ্যার LCM (লসাগু) হলো সবচেয়ে ছোট সংখ্যা, যাকে দুটোই ভাগ করে। একটি বাস প্রতি ১২ মিনিটে আসে, আরেকটি প্রতি ১৮ মিনিটে; সকাল ৮টায় দুটি একসাথে ছাড়লে আবার একসাথে আসবে lcm(১২, ১৮) = ৩৬ মিনিট পরে। সূত্র: lcm(a, b) = a × b ÷ gcd(a, b).

সূত্রটি কোডে a * b / gcd(a, b) লিখলে একটি লুকানো বিপদ থাকে। ধরুন a = 100000, b = 99999 — দুটোই int-এ সহজে আঁটে, আর উত্তর 9999900000 (gcd = 1). কিন্তু a * b আগে হিসাব হয়, আর সেটি int-এর সীমা (প্রায় ২১৪ কোটি) অনেক ছাড়িয়ে যায় — signed overflow, অর্থাৎ undefined behavior. নিরাপদ ক্রম হলো আগে ভাগ, পরে গুণ: a / gcd(a, b) * b. ভাগটি সবসময় নিঃশেষে হয়, তাই কোনো তথ্য হারায় না, আর মাঝের সংখ্যা কখনো চূড়ান্ত উত্তরের চেয়ে বড় হয় না। চূড়ান্ত উত্তরটিই বড় হলে ফলাফল long long-এ রাখুন।

৬ · Sieve of Eratosthenes — prime ছেঁকে তোলা

একটি সংখ্যা যাচাই করতে √n পর্যন্ত ভাগ যথেষ্ট। কিন্তু যদি ১ থেকে ১০ লাখ পর্যন্ত সব prime লাগে? প্রত্যেককে আলাদা যাচাই করলে অনেক কাজ বারবার হয়। এর চেয়ে অনেক চতুর পথ হলো Sieve of Eratosthenes — চালুনি দিয়ে চাল থেকে কাঁকর ছেঁকে ফেলার মতো, যৌগিক সংখ্যাগুলো ছেঁকে ফেলে দেওয়া।

Eratosthenes ছিলেন খ্রিস্টপূর্ব তৃতীয় শতকের গ্রিক পণ্ডিত, আলেকজান্দ্রিয়ার বিখ্যাত গ্রন্থাগারের প্রধান। তিনি ছায়া মেপে পৃথিবীর পরিধির হিসাব করেছিলেন বলেও বিখ্যাত। ছাঁকনি-পদ্ধতিটি তাঁর নামে পরিচিত।

নিয়মটি সহজ: সবচেয়ে ছোট না-কাটা সংখ্যাটি prime. তার সব গুণিতক কেটে দিন। তারপর পরের না-কাটা সংখ্যা, আবার তার গুণিতক কাটা। নিচে ১ থেকে ৩০ পর্যন্ত ৬টি কলামে সাজানো আছে। লাল মানে কাটা পড়েছে (prime নয়):

ছাঁকনির অবস্থা

এখনকার prime p
কাটা শুরু
এই ধাপে নতুন কাটা
বাকি (প্রার্থী)

শুরু। ২ থেকে ৩০ পর্যন্ত ২৯টি সংখ্যা — সবাই এখন “সম্ভাব্য prime” হিসেবে আছে। শুধু ১-কে শুরুতেই কেটে দেওয়া হলো, কারণ ১ prime নয়। কোডে এটি একটি char array, যার প্রতিটি ঘর শুরুতে 0 (“এখনো কাটা হয়নি”)।
p = 2. সবচেয়ে ছোট না-কাটা সংখ্যা ২, তাই ২ prime. এবার ৪, ৬, ৮ … ৩০ — দুই-দুই লাফে সব জোড় সংখ্যা কাটা। খেয়াল করুন, ৬টি কলামের মধ্যে চতুর্থ আর ষষ্ঠ কলাম পুরো লাল, আর দ্বিতীয় কলামে শুধু ২ বেঁচে আছে। একটিও ভাগ লাগেনি।
p = 3, কাটা শুরু ৯ থেকে। ৬ কেন নয়? কারণ ৬ = ২ × ৩, ২-এর ধাপেই কাটা পড়েছে। ৩-এর যেকোনো গুণিতক k × ৩, যেখানে k < ৩, তার ভেতরে ৩-এর চেয়ে ছোট একটি উৎপাদক আছে — তাই আগেই কাটা। নতুন কাটা পড়ল ৯, ১৫, ২১, ২৭; ১২, ১৮, ২৪, ৩০ আগে থেকেই লাল। এখন তৃতীয় কলামেও শুধু ৩ বেঁচে আছে।
p = 5 (৪ আগেই কাটা, তাই বাদ)। শুরু ৫ × ৫ = ২৫ থেকে। ১০, ১৫, ২০ আগেই কাটা হয়েছে ২ বা ৩-এর ধাপে। নতুন কাটা শুধু ২৫ (৩০ আগে থেকেই লাল)।
এখানেই শেষ — বাকিরা সবাই prime. পরের প্রার্থী ৭-এর জন্য কাটা শুরু হতো ৪৯ থেকে, যা ৩০-এর বাইরে। তাই p × p > n হলেই কাজ শেষ। বাকি ১০টি: ২, ৩, ৫, ৭, ১১, ১৩, ১৭, ১৯, ২৩, ২৯. আরও খেয়াল করুন — ২ আর ৩ ছাড়া প্রতিটি prime প্রথম বা পঞ্চম কলামে, অর্থাৎ ৬-এর কোনো গুণিতকের ঠিক এক আগে বা এক পরে। এটি কাকতালীয় নয়: বাকি কলামের সব সংখ্যা ২ বা ৩ দিয়ে বিভাজ্য।

কত দ্রুত? মোট কাটার সংখ্যা মোটামুটি n/2 + n/3 + n/5 + n/7 + …, যা বাড়ে n log log n হারে। log log n এত ধীরে বাড়ে যে ১০০ কোটিতেও এর মান ৩-এর কাছাকাছি (স্বাভাবিক লগারিদমে) — অর্থাৎ বাস্তবে প্রায় n-এর অনুপাতে। ১০ লাখ পর্যন্ত সব prime (মোট ৭৮,৪৯৮টি) একটি সাধারণ ল্যাপটপে এক সেকেন্ডের অনেক কম সময়ে পাওয়া যায়।

এবার আসল C. একই প্রোগ্রামে ছাঁকনি আর উপরের gcd/lcm:

#include <stdio.h>
#define N 30

int gcd(int a, int b) {
    while (b != 0) { int r = a % b; a = b; b = r; }
    return a;
}

int main(void) {
    char composite[N + 1] = {0};            /* 0 = still a candidate */
    for (int p = 2; p * p <= N; p++)
        if (!composite[p])                  /* p is prime */
            for (int k = p * p; k <= N; k += p) composite[k] = 1;
    printf("primes up to %d:", N);
    for (int i = 2; i <= N; i++) if (!composite[i]) printf(" %d", i);
    int a = 252, b = 105, g = gcd(a, b);
    long long l = (long long)(a / g) * b;   /* divide first, then multiply */
    printf("\ngcd(%d, %d) = %d, lcm = %lld\n", a, b, g, l);
    return 0;
}

Array-র আকার N + 1, যাতে composite[30]-ও বৈধ ঘর হয় — এখানে ১ কম দিলে ক্লাসিক off-by-one ভুল, আর শেষ সংখ্যাটি array-র বাইরে লেখা হবে। বাইরের লুপ চলে p * p <= N পর্যন্ত, আর ভেতরের লুপ শুরু হয় p * p থেকে — ঠিক যেমন ডায়াগ্রামে দেখলেন। আউটপুট: primes up to 30: 2 3 5 7 11 13 17 19 23 29 এবং gcd(252, 105) = 21, lcm = 1260. LCM-এর লাইনে আগে a / g = 12, তারপর long long-এ নিয়ে 105 দিয়ে গুণ — বড় সংখ্যাতেও এই ক্রম নিরাপদ। N অনেক বড় করলে array-টি global বা static করুন, নইলে stack-এ জায়গা না-ও আঁটতে পারে।

৭ · Modular arithmetic — ঘড়ির অঙ্ক

এখন রাত ১০টা। ৫ ঘণ্টা পর কয়টা বাজবে? ১৫টা নয় — ৩টা। ঘড়ি ১২-তে পৌঁছে আবার শুরু থেকে গোনে। অর্থাৎ (১০ + ৫) % ১২ = ৩. সপ্তাহের দিনও তাই: আজ শুক্রবার হলে ১০০ দিন পর কী বার? ১০০ % ৭ = ২, তাই শুক্রবারের দুই দিন পর — রবিবার। এই “ঘুরে আসা” অঙ্কের নাম modular arithmetic, আর যে সংখ্যায় ঘুরে আসে (১২ বা ৭), তাকে বলে modulus.

দুটি সংখ্যার ভাগশেষ m দিয়ে একই হলে বলি তারা “m-এর সাপেক্ষে সমান” — একে বলে congruence, লেখা হয় ১৭ ≡ ৫ (mod ১২). এই প্রতীক আর ধারণাকে গুছিয়ে গণিতের একটি শাখা বানান জার্মান গণিতবিদ Carl Friedrich Gauss, ১৮০১ সালে প্রকাশিত তাঁর বই Disquisitiones Arithmeticae-তে।

তিনটি সোনালি নিয়ম

(a + b) % m = ((a % m) + (b % m)) % m
(a − b) % m = ((a % m) − (b % m) + m) % m
(a × b) % m = ((a % m) × (b % m)) % m

এর মানে হলো, যোগ, বিয়োগ আর গুণের প্রতিটি ধাপে ভাগশেষ নিয়ে নিলেও শেষ উত্তর একই থাকে। এটি কেন জরুরি? ধরুন একটি সমস্যার উত্তর ২^১০০০ — একটি ৩০২ অঙ্কের সংখ্যা, কোনো C টাইপে আঁটে না। কিন্তু যদি প্রশ্ন হয় “উত্তরের ভাগশেষ কত”, তাহলে প্রতিটি গুণের পরে % m নিয়ে সংখ্যাকে সবসময় m-এর চেয়ে ছোট রাখা যায়।

ভাগের কোনো সহজ নিয়ম নেই। (a / b) % m সাধারণত ((a % m) / (b % m)) % m-এর সমান নয়। যেমন m = 7 হলে (12 / 4) % 7 = 3, কিন্তু 12 % 7 = 5, 4 % 7 = 4, আর 5 / 4 = 1. ভাগের জন্য লাগে আলাদা কৌশল — modular inverse, যা পরের অংশে দেখব।

কনটেস্টে কেন “answer modulo 1,000,000,007”?

প্রোগ্রামিং কনটেস্টে প্রায়ই দেখবেন: “উত্তর অনেক বড় হতে পারে, তাই 10⁹ + 7 দিয়ে ভাগশেষ দিন।” এই নির্দিষ্ট সংখ্যাটি বেছে নেওয়ার তিনটি কারণ:

এটি prime. Prime modulus-এ শূন্য ছাড়া প্রতিটি সংখ্যার “ভাগ” (inverse) পাওয়া যায় — নিচে দেখবেন।
এটি int-এ আঁটে, এমনকি দুটির যোগফলও। 1,000,000,007 < 2³¹ − 1 = 2,147,483,647. দুটি ভাগশেষ যোগ করলেও সর্বোচ্চ প্রায় ২০০ কোটি, তাও আঁটে।
দুটির গুণফল 64-bit-এ আঁটে। সর্বোচ্চ প্রায় 10¹⁸, আর long long-এর সীমা প্রায় 9.2 × 10¹⁸. তাই a * b % MOD নিরাপদ — যদি গুণটি long long-এ হয়।

C-র `%` আর ঋণাত্মক সংখ্যা

পর্ব ০৭-এ দেখেছি, C99 থেকে ভাগফল শূন্যের দিকে কাটা হয়, তাই ভাগশেষের চিহ্ন হয় বাঁ পাশের সংখ্যার মতো: -7 % 5 = -2, গণিতের ৩ নয়। ঘড়ি পেছানো বা বিয়োগের পরে ভাগশেষে এই ঋণাত্মক মান array-র বাইরের index হয়ে বাগ তৈরি করে। নিরাপদ সূত্র:

((x % m) + m) % m → সবসময় 0 থেকে m − 1

প্রথম % মানটিকে −(m − 1) থেকে m − 1-এর মধ্যে আনে, + m সেটিকে ধনাত্মক করে, আর শেষ % ধনাত্মক x-এর ক্ষেত্রে বাড়তি m-টি সরিয়ে দেয়।

৮ · দ্রুত ঘাত — বারবার বর্গ, দরকার হলে গুণ

3¹³ mod 1000 বের করতে সরল পথ: ১-কে ৩ দিয়ে ১৩ বার গুণ, প্রতিবার % 1000. ১৩ বার চলে। কিন্তু RSA-তে ঘাতটি হতে পারে ৬০০ অঙ্কের একটি সংখ্যা — তত বার গুণ করতে মহাবিশ্বের বয়সও যথেষ্ট নয়। তাহলে উপায়?

কৌশলটি হলো ঘাতকে বাইনারিতে ভাঙা। ১৩ = ৮ + ৪ + ১ (বাইনারিতে 1101), তাই 3¹³ = 3⁸ × 3⁴ × 3¹. আর 3, 3², 3⁴, 3⁸ পাওয়া যায় শুধু বারবার বর্গ করে। ঘাতের যে বিট 1, সেই ঘাতটি উত্তরে গুণ করা হয়। এই পদ্ধতির নাম modular exponentiation বা square-and-multiply. লুপ চলে ঘাতের বিটের সংখ্যার সমান — অর্থাৎ O(log n) বার।

1long long modpow(long long b, long long e, long long m) {2    long long r = 1;  b %= m;3    while (e > 0) {4        if (e & 1) r = r * b % m;5        b = b * b % m;6        e >>= 1;7    }8    return r;9}

প্রতিটি ঘুরে আসার পরে

e (বাইনারি)
এই বিট
b (= 3^?)
r

শুরু। r = 1 (এখনো কিছু গুণ হয়নি), b = 3, e = 13 = বাইনারিতে 1101. লুপটি ডান দিক থেকে একটি একটি বিট পড়বে। b %= m শুরুতেই b-কে m-এর ছোট করে রাখে।
সবচেয়ে ডানের বিট 1. e & 1 সত্য (পর্ব ০৯-এর বিট-কৌশল), তাই r = 1 × 3 = 3 — উত্তরে 3¹ ঢুকল। তারপর b বর্গ হয়ে 9 = 3², আর bit shift e >>= 1 দিয়ে e হলো 6 (110).
পরের বিট 0. 3² উত্তরে লাগবে না, তাই r অপরিবর্তিত, 3. শুধু b বর্গ: 81 = 3⁴. e হলো 3 (11).
বিট 1. r = 3 × 81 = 243 — এখন r-এ আছে 3¹⁺⁴ = 3⁵. b = 81 × 81 = 6561, ভাগশেষ নিয়ে 561 (এটি 3⁸ % 1000). e হলো 1.
শেষ বিট 1. r = 243 × 561 = 136323, % 1000 = 323. এখন r-এ 3¹⁺⁴⁺⁸ = 3¹³-এর ভাগশেষ। b আরেকবার বর্গ হয় (721), কিন্তু আর লাগবে না। e হলো 0.
উত্তর 323. যাচাই: 3¹³ = 1594323, শেষ তিন অঙ্ক 323 — মিলে গেছে। মোট ৪ বার ঘুরে আসা, ১৩ বার নয়। ঘাতটি 10¹⁸ হলেও মাত্র ৬০ বার; ৬০০ অঙ্কের ঘাতে প্রায় ২,০০০ বার। গুণের সংখ্যা ঘাতের মানের সাথে নয়, তার অঙ্কসংখ্যার সাথে বাড়ে।

Modular inverse — mod-এর জগতে “ভাগ”

সাধারণ অঙ্কে ৩ দিয়ে ভাগ মানে ১/৩ দিয়ে গুণ। Mod-এর জগতে ১/৩-এর বদলে এমন একটি সংখ্যা x খুঁজি, যাতে 3 * x % m == 1. একে বলে 3-এর modular inverse. এটি থাকে কেবল তখনই, যখন gcd(৩, m) = ১.

m যদি prime হয়, তাহলে খুঁজে পাওয়ার একটি চমৎকার শর্টকাট আছে — Fermat's little theorem. ফরাসি গণিতবিদ Pierre de Fermat ১৬৪০ সালে একটি চিঠিতে এটি উল্লেখ করেন: p prime আর a যদি p দিয়ে বিভাজ্য না হয়, তাহলে a^p−1 ≡ ১ (mod p). দুই পাশকে a দিয়ে “ভাগ” করলে পাই: a-এর inverse = a^p−2 mod p — আর সেটি modpow দিয়ে এক লাইনেই বের হয়। m prime না হলে লাগে extended Euclid — GCD-রই একটি বর্ধিত রূপ, যা আপনি Discrete Math কোর্সে বিস্তারিত পাবেন।

#include <stdio.h>
#define MOD 1000000007LL
long long modpow(long long b, long long e, long long m) {
    long long r = 1;  b %= m;
    while (e > 0) {
        if (e & 1) r = r * b % m;   /* this bit is 1: multiply it in */
        b = b * b % m;              /* square for the next bit */
        e >>= 1;
    }
    return r;
}
int main(void) {
    long long slow = 1, inv3 = modpow(3, MOD - 2, MOD);     /* Fermat */
    for (int i = 0; i < 13; i++) slow = slow * 3 % 1000;  /* naive check */
    printf("3^13 mod 1000: fast = %lld, slow = %lld\n", modpow(3, 13, 1000), slow);
    printf("2^(10^18) mod p = %lld\n", modpow(2, 1000000000000000000LL, MOD));
    printf("inverse of 3 = %lld, 3 * inv = %lld\n", inv3, 3 * inv3 % MOD);
    int x = -7, m = 5;
    printf("-7 %% 5 = %d, fixed = %d\n", x % m, ((x % m) + m) % m);
    return 0;
}

প্রথম লাইনে দ্রুত আর সরল পদ্ধতি পাশাপাশি — দুটোই 323 দিলে বোঝা যায় modpow ঠিক আছে। দ্বিতীয় লাইনে ঘাত 10¹⁸: সরল লুপে এটি শেষ হতো না, অথচ modpow মাত্র ৬০ বার ঘুরে উত্তর দেয় 719476260. তৃতীয় লাইনে Fermat-এর সূত্রে 3-এর inverse পাওয়া গেল 333333336; যাচাই: 3 × 333333336 = 1000000008, যার ভাগশেষ 1. শেষ লাইনে -7 % 5 দেয় -2, আর সংশোধিত সূত্র দেয় 3. সব ভ্যারিয়েবল long long — কারণ r * b প্রায় 10¹⁸ পর্যন্ত যেতে পারে। (printf-এ %% মানে একটি % চিহ্ন।)

m যদি 10¹⁸-এর মতো বড় হয়, তাহলে long long-ও যথেষ্ট নয় — দুটি 10¹⁸-এর গুণফল 10³⁶. GCC আর Clang 64-bit সিস্টেমে unsigned __int128 নামে একটি 128-bit টাইপ দেয়; এটি C standard-এর অংশ নয়, compiler-এর নিজস্ব সুবিধা (extension), তাই সব compiler-এ পাবেন না।

৯ · বাস্তবে নাম্বার থিওরি — RSA, Diffie–Hellman আর চেকসাম

ব্রাউজারে ব্যাংকের ওয়েবসাইটের পাশে তালার চিহ্নটির পেছনে এই পর্বের প্রায় প্রতিটি ধারণা কাজ করছে।

🔐 RSA (১৯৭৭)

MIT-র Rivest, Shamir আর Adleman-এর তৈরি RSA. দুটি বিশাল prime p, q গুণ করে n বানানো হয় — গুণ করা সহজ, কিন্তু শুধু n দেখে p আর q খুঁজে বের করা (factoring) আজকের কম্পিউটারে কার্যত অসম্ভব। Key বানাতে লাগে gcd আর modular inverse, আর এনক্রিপশন মানেই modpow.

ডিজিটাল স্বাক্ষর, সার্টিফিকেট

🤝 Diffie–Hellman (১৯৭৬)

Whitfield Diffie আর Martin Hellman দেখান, দুজন মানুষ সবার সামনে কথা বলেও একটি গোপন চাবিতে একমত হতে পারেন। প্রত্যেকে একটি গোপন ঘাত বেছে নিয়ে g^a mod p পাঠান। Diffie–Hellman-এর নিরাপত্তা নির্ভর করে এই ধারণার ওপর যে ফল দেখে ঘাতটি বের করা খুব কঠিন।

HTTPS সংযোগের শুরু

দুটিই public-key cryptography-র উদাহরণ: একটি চাবি সবাইকে দেওয়া যায়, আরেকটি থাকে গোপন। দুটির ভিত্তিই একটি “একমুখী রাস্তা” — এক দিকে যাওয়া সহজ (গুণ, modpow), উল্টো দিকে ফেরা অসম্ভব কঠিন (factoring, ঘাত খোঁজা)। গভীরে যেতে চাইলে Cybersecurity কোর্সটি দেখুন।

এই পর্বের modpow দিয়ে নিজের এনক্রিপশন বানাবেন না। আসল RSA-তে লাগে ২,০৪৮ বিট বা তার বেশি সংখ্যা, নিরাপদ random সংখ্যা, padding, আর এমন কোড যার চলার সময় গোপন বিটের ওপর নির্ভর করে না। বাস্তবে OpenSSL বা libsodium-এর মতো পরীক্ষিত library ব্যবহার করুন।

চেকসাম — ছোট ভুল ধরার ভাগশেষ

বইয়ের পেছনের ISBN নম্বর বা আপনার ব্যাংক কার্ডের নম্বরের শেষ অঙ্কটি এলোমেলো নয়। এটি একটি checksum — বাকি অঙ্কগুলো থেকে হিসাব করে বসানো একটি যাচাই-অঙ্ক। কেউ একটি অঙ্ক ভুল টাইপ করলে হিসাব আর মেলে না।

ISBN-13: অঙ্কগুলোকে পালাক্রমে ১ আর ৩ দিয়ে গুণ করে যোগ করলে যোগফল ১০ দিয়ে বিভাজ্য হতে হবে। পুরোনো ISBN-10-এ ব্যবহার হতো ১১ দিয়ে ভাগশেষ।
কার্ড নম্বর: বেশিরভাগ ক্রেডিট ও ডেবিট কার্ড নম্বর Luhn algorithm মেনে চলে — IBM-এর প্রকৌশলী Hans Peter Luhn-এর তৈরি। প্রতি দ্বিতীয় অঙ্ক দ্বিগুণ করে (৯-এর বেশি হলে ৯ বাদ দিয়ে) সব যোগ করলে যোগফল ১০ দিয়ে বিভাজ্য হতে হয়। এটি যেকোনো একটি অঙ্কের ভুল ধরে।

মনে রাখুন: চেকসাম ভুলবশত হওয়া টাইপো ধরে, প্রতারণা ঠেকায় না — Luhn মেলে এমন নম্বর যে কেউ বানাতে পারে।

১০ · AI-এর যুগে greedy ও নাম্বার থিওরি — যা যাচাই করবেন

AI-কে কোনো অপ্টিমাইজেশন সমস্যা দিলে সে প্রায়ই খুব আত্মবিশ্বাসী একটি greedy সমাধান দেয় — সুন্দর কোড, দু-একটি উদাহরণে সঠিক উত্তর। সমস্যা হলো, greedy যখন ভুল করে, তখন সে crash করে না, warning দেয় না — শুধু চুপচাপ একটু খারাপ উত্তর দেয়। নাম্বার থিওরির কোডে একই ফাঁদ overflow.

AI-এর ভুল	কেমন দেখায়	কীভাবে ধরবেন
প্রমাণ ছাড়া greedy	“সবচেয়ে বড় কয়েন আগে” — যেকোনো কয়েন-ব্যবস্থার জন্য	ছোট সব ইনপুটে brute force বা DP-র সাথে মিলিয়ে দেখুন
ভুল মাপকাঠিতে সাজানো	Activity selection-এ শুরুর সময় বা দৈর্ঘ্য দিয়ে sort	“লম্বা কিন্তু আগে শুরু” ধরনের ইনপুট দিন
`a * b % m`-এ overflow	`int a, b;` দিয়ে গুণ, পরে `long long`-এ রাখা	m-এর কাছাকাছি মান দিয়ে চালান; গুণের আগেই টাইপ বড় কি না দেখুন
ঋণাত্মক ভাগশেষ	`(a - b) % m` সরাসরি index হিসেবে	a < b এমন ইনপুট দিন
Sieve-এ off-by-one	`char s[N]` কিন্তু লুপ `k <= N` পর্যন্ত	N নিজেই prime হলে (যেমন 29) বা যৌগিক হলে, দুটোই দেখুন

সবচেয়ে শক্তিশালী অস্ত্রটির নাম brute force যাচাই: একটি ধীর কিন্তু নিশ্চিতভাবে সঠিক সমাধান লিখুন (সব সম্ভাবনা যাচাই), তারপর হাজারটা ছোট এলোমেলো ইনপুটে দ্রুত সমাধানের সাথে মেলান। একটিও অমিল পেলে সেটিই আপনার counterexample. পরের পর্বে এ নিয়ে আরও দেখব।

AI-কে greedy সমাধান চাইলে প্রমাণ আর যাচাই একসাথে চেয়ে নিন। শেষ দুটি লাইন খেয়াল করুন — AI-কে নিজের ভুল খুঁজতে বাধ্য করছে:

আমি C-তে এই সমস্যার সমাধান চাই: [সমস্যার বর্ণনা ও ইনপুটের সীমা] ১. তুমি যদি greedy পদ্ধতি দাও, তাহলে আগে সহজ বাংলায় বলো কেন greedy এখানে সবসময় সেরা উত্তর দেয় (exchange argument দিয়ে)। নিশ্চিত না হলে সরাসরি বলো। ২. সব গুণের জায়গায় overflow হতে পারে কি না দেখাও; দরকার হলে long long ব্যবহার করো, আর ভাগশেষ যেন কখনো ঋণাত্মক না হয়। ৩. একটি আলাদা brute force ফাংশন লেখো, আর ছোট এলোমেলো ইনপুটে দুটির উত্তর মিলিয়ে দেখার একটি main() দাও। ৪. greedy যেখানে ভুল করতে পারে এমন একটি সম্ভাব্য ইনপুট নিজে খুঁজে বের করার চেষ্টা করো।

AI-এর দেওয়া greedy বা নাম্বার থিওরির কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

Greedy কেন সঠিক, তার একটি যুক্তি আমি নিজের ভাষায় বলতে পারি — শুধু “উদাহরণে চলেছে” নয়
ছোট সব ইনপুটে brute force-এর সাথে মিলিয়েছি, একটিও অমিল নেই
প্রতিটি a * b গুণের আগে অন্তত একটি অপারেন্ড long long; m-এর কাছাকাছি মান দিয়ে পরীক্ষা করেছি
বিয়োগের পরে ভাগশেষ ((x % m) + m) % m দিয়ে ধনাত্মক করা হয়েছে
Array-র আকার N + 1, আর ০, ১, ২ ও N-এর মতো edge case আলাদা করে চালিয়ে দেখেছি

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন। এগুলোই আপনাকে কোড-লেখক থেকে সিস্টেম-চিন্তক বানাবে।

প্র ০১একটি সমস্যায় greedy কাজ করবে কি না, আগে থেকে বুঝবেন কীভাবে?

কোনো জাদুর বোতাম নেই, কিন্তু কয়েকটি নির্ভরযোগ্য সংকেত আছে। পাঠ্যবইয়ে এগুলোকে দুটি নামে ডাকা হয়:

Greedy-choice property: প্রথম ধাপের greedy পছন্দটি কোনো না কোনো সেরা সমাধানের অংশ। Activity selection-এ exchange argument দিয়ে আমরা ঠিক এটিই দেখিয়েছি।
Optimal substructure: প্রথম পছন্দের পরে যে ছোট সমস্যাটি থাকে, তার সেরা সমাধান আর প্রথম পছন্দ মিলে পুরো সমস্যার সেরা সমাধান হয়। এই গুণটি DP-তেও লাগে — পার্থক্য হলো DP প্রতিটি ধাপে সব পছন্দ যাচাই করে, greedy একটিই নেয়।

গণিতবিদেরা আরও গভীরে গিয়ে একটি কাঠামো খুঁজে পেয়েছেন, যার নাম matroid. মোটামুটি বললে, যে সমস্যার “বৈধ বাছাই”-গুলো কিছু নির্দিষ্ট নিয়ম মানে (যেমন বৈধ বাছাইয়ের যেকোনো অংশও বৈধ, আর ছোট বৈধ বাছাইকে বড়টি থেকে একটি জিনিস এনে বাড়ানো যায়), সেখানে ওজন যা-ই হোক, “সবচেয়ে ভারী আগে” greedy সবসময় সেরা। Kruskal-এর অ্যালগরিদম ঠিক এই কারণেই সঠিক। এটি উচ্চতর কোর্সের বিষয়; এখানে শুধু জেনে রাখুন যে “greedy কখন কাজ করে” প্রশ্নটির একটি সত্যিকারের গাণিতিক উত্তর আছে।

বাস্তবে একজন প্রোগ্রামার যা করেন: প্রথমে একটি counterexample খোঁজার চেষ্টা করেন — ছোট, অদ্ভুত ইনপুট নিয়ে খাতায়। না পেলে একটি brute force লিখে কয়েক হাজার এলোমেলো ছোট ইনপুটে মিলিয়ে দেখেন। তারপরও নিশ্চিত হতে exchange argument-এর মতো একটি যুক্তি দাঁড় করান। কনটেস্টে প্রচুর “Wrong Answer” আসে ঠিক এই ধাপ বাদ দেওয়ার কারণে — greedy-টা “মনে হচ্ছিল” ঠিক।

একটি ভালো লক্ষণ হলো: যদি সমস্যায় “বড় জিনিস ছেড়ে দিয়ে পরে লাভ” সম্ভব হয় (যেমন {১, ৩, ৪}-এ ৪ ছেড়ে দুটি ৩ নেওয়া), তাহলে greedy নিয়ে সন্দেহ করুন। ব্যাগে সীমিত জায়গায় সবচেয়ে দামি জিনিস ভরার 0/1 knapsack-এ greedy ব্যর্থ হয়, অথচ জিনিস কেটে ভাগ করা গেলে (fractional knapsack) “প্রতি কেজিতে সবচেয়ে দামি আগে” নিখুঁত কাজ করে — ছোট একটি শর্ত বদলালেই উত্তর বদলে যায়।

মূল উপলব্ধি: Greedy একটি অনুমান, যতক্ষণ না প্রমাণ বা ব্যাপক যাচাই তাকে সত্য বানায়। প্রমাণ করুন, অথবা অন্তত brute force দিয়ে ভাঙার চেষ্টা করুন।

প্র ০২RSA কেন নিরাপদ? আর কোয়ান্টাম কম্পিউটার কি একে ভেঙে ফেলবে?

RSA-র নিরাপত্তা একটি অসমতার ওপর দাঁড়িয়ে: দুটি বড় prime গুণ করা খুব সহজ, কিন্তু গুণফল থেকে prime দুটি ফিরে পাওয়া খুব কঠিন। ৩০০ অঙ্কের দুটি prime-এর গুণ আপনার ফোন এক সেকেন্ডের অনেক কম সময়ে করে। কিন্তু ৬০০ অঙ্কের সেই গুণফলকে ভাঙার কোনো দ্রুত পদ্ধতি জানা নেই।

খেয়াল করুন, “জানা নেই” আর “অসম্ভব প্রমাণিত” এক কথা নয়। কেউ গাণিতিকভাবে প্রমাণ করেননি যে factoring কঠিন — শুধু কয়েক দশক ধরে বিশ্বের সেরা গণিতবিদেরা চেষ্টা করেও দ্রুত সাধারণ পদ্ধতি পাননি। প্রকাশ্য রেকর্ডে ২০২০ সালে ৮২৯-বিটের একটি RSA সংখ্যা (RSA-250) ভাঙা হয়েছে, তাতে হাজার হাজার CPU-বছরের সমান হিসাব লেগেছিল। আজকের ২,০৪৮-বিট key তার চেয়ে বহু গুণ কঠিন।

এখানে এই পর্বের অ্যালগরিদমগুলোর ভূমিকা স্পষ্ট দেখা যায়। Key তৈরির জন্য বড় prime খুঁজতে লাগে দ্রুত prime-পরীক্ষা (যা modpow-এর ওপর চলে; sieve এত বড় সংখ্যায় চলে না)। Public ও private ঘাত বানাতে লাগে gcd আর modular inverse; আর এনক্রিপশন ও ডিক্রিপশন দুটোই চলে modpow দিয়ে। অর্থাৎ যা সহজ হওয়া দরকার, তার প্রতিটির জন্য আমাদের হাতে O(log n) পদ্ধতি আছে; আর যা কঠিন হওয়া দরকার (factoring), তার জন্য নেই।

কোয়ান্টাম হুমকি: ১৯৯৪ সালে Peter Shor দেখান, যথেষ্ট বড় ও নির্ভুল একটি কোয়ান্টাম কম্পিউটার factoring আর Diffie–Hellman-এর মূল সমস্যা দুটোই দ্রুত সমাধান করতে পারবে। আজকের কোয়ান্টাম যন্ত্র সেই আকারের ধারেকাছেও নেই, কিন্তু ঝুঁকিটি বাস্তব — কেউ আজকের এনক্রিপ্ট করা ডেটা জমিয়ে রেখে ভবিষ্যতে খুলতে পারে। তাই ২০২৪ সালে মার্কিন মান-নির্ধারক সংস্থা NIST কোয়ান্টাম-প্রতিরোধী (post-quantum) এনক্রিপশনের প্রথম মানগুলো প্রকাশ করেছে, যেগুলো সম্পূর্ণ ভিন্ন গাণিতিক সমস্যার ওপর দাঁড়ানো।

মূল উপলব্ধি: আধুনিক ক্রিপ্টোগ্রাফি “এক দিকে সহজ, উল্টো দিকে কঠিন” — এমন সমস্যার খোঁজ। নিরাপত্তা একটি গাণিতিক অনুমানের ওপর ভর করে, আর প্রকৌশলীদের সবসময় পরের অনুমানের জন্য প্রস্তুত থাকতে হয়।

প্র ০৩কনটেস্টে 1,000,000,007 আর 998,244,353 — এই দুটি অদ্ভুত সংখ্যাই কেন বারবার আসে?

কনটেস্টের আয়োজকেরা চান উত্তরটি বিশাল হলেও যাচাই করা সহজ হোক। “উত্তরের ভাগশেষ দিন” বললে প্রতিযোগীর কাজ হয় প্রতিটি ধাপে ভাগশেষ রাখা, আর বিচারকের কাজ একটিমাত্র সংখ্যা মেলানো। কিন্তু m যেকোনো সংখ্যা হলে চলে না — কয়েকটি শর্ত পূরণ করতে হয়।

Prime হতে হবে: তাহলে শূন্য ছাড়া প্রতিটি সংখ্যার inverse আছে, আর ভাগ লাগে এমন সূত্র (যেমন nCr = n! / (r! (n−r)!)) Fermat দিয়ে হিসাব করা যায়। m যৌগিক হলে কিছু সংখ্যার inverse থাকে না, আর সূত্র ভেঙে পড়ে।
আকার ঠিক হতে হবে: 10⁹ + 7 এত বড় যে এলোমেলো ভুল উত্তর কাকতালীয়ভাবে মিলে যাওয়ার সম্ভাবনা নগণ্য, আবার এত ছোট যে দুটি ভাগশেষের যোগফল 32-bit int-এ আর গুণফল 64-bit-এ আঁটে। 10⁹ + 7 মনে রাখাও সহজ — ১-এর পরে আটটি শূন্য, তারপর ৭.

998244353 কেন? এটিও prime, আর এর একটি বিশেষ গঠন আছে: 998244353 = 119 × 2²³ + 1. অর্থাৎ (m − 1)-এর ভেতরে ২-এর একটি বড় ঘাত লুকিয়ে আছে। Number Theoretic Transform (NTT) নামের একটি অ্যালগরিদম — বিশাল বহুপদী বা বিশাল সংখ্যা দ্রুত গুণ করার কৌশল, যা FFT-র “mod-জগতের” রূপ — ঠিক এই গঠন চায়। তাই যেসব সমস্যায় NTT লাগতে পারে, সেখানে 998244353 দেখবেন।

একটি নিরাপত্তা-দিকও আছে। কোনো কোনো কনটেস্টে প্রতিযোগীরা একে অপরের কোড “hack” করতে পারেন। সবাই যদি 10⁹ + 7 দিয়ে hash বানায়, তাহলে কেউ ইচ্ছে করে collision ঘটানো ইনপুট বানাতে পারে (পর্ব ৩৭-এর hash flooding-এর কথা মনে করুন)। তাই অভিজ্ঞরা hashing-এর জন্য নিজের এলোমেলো বড় prime বা দুটি আলাদা modulus ব্যবহার করেন — কিন্তু উত্তর দেওয়ার জন্য প্রশ্নে যা বলা আছে, সেটাই মানতে হয়।

মূল উপলব্ধি: একটি “জাদুর সংখ্যা” আসলে কয়েকটি প্রকৌশল-শর্তের মিলনবিন্দু — prime হওয়া, টাইপের সীমায় আঁটা, আর বিশেষ অ্যালগরিদমের প্রয়োজন। সংখ্যাটি মুখস্থ করার চেয়ে শর্তগুলো বোঝা বেশি কাজের।

প্র ০৪Greedy কি শুধু ক্লাসরুমের জিনিস, নাকি বাস্তব সিস্টেমেও চলে?

Greedy আপনার চারপাশের সফটওয়্যারে সবখানে — কখনো প্রমাণিত সেরা হিসেবে, কখনো “যথেষ্ট ভালো আর দ্রুত” আন্দাজ হিসেবে।

ফাইল সংকোচন: Huffman coding আজও ZIP, gzip ও PNG-র DEFLATE পদ্ধতিতে আর JPEG-এ ব্যবহার হয়। আপনি প্রতিদিন যত ছবি দেখেন, তার অনেকগুলোর ভেতরে Huffman-এর greedy গাছ আছে।
ইন্টারনেট রাউটিং: বড় নেটওয়ার্কের ভেতরে পথ খোঁজার OSPF প্রোটোকল প্রতিটি রাউটারে Dijkstra-র greedy অ্যালগরিদম চালায়। ম্যাপ অ্যাপের পথ খোঁজাও এর বংশধর।
নেটওয়ার্ক নকশা: গ্রামে বিদ্যুতের লাইন বা অফিসে তার সবচেয়ে কম খরচে জোড়ার প্রশ্নে Kruskal বা Prim-এর greedy অ্যালগরিদম প্রমাণিত সেরা উত্তর দেয়।
কাজের সময়সূচি: অপারেটিং সিস্টেম আর ক্লাউড সার্ভারে “সবচেয়ে ছোট কাজ আগে” (Shortest Job First) গড় অপেক্ষার সময় কমায় — যদিও বাস্তবে কাজের দৈর্ঘ্য আগে জানা থাকে না, তাই আন্দাজ করতে হয়।

Cache-এর গল্পটি সবচেয়ে শিক্ষণীয়। Cache ভরে গেলে কোন জিনিস বের করবেন? ১৯৬৬ সালে IBM-এর László Bélády দেখান, সেরা নিয়ম হলো একটি greedy: “যে জিনিস ভবিষ্যতে সবচেয়ে দেরিতে লাগবে, তাকে বের করে দিন।” সমস্যা হলো ভবিষ্যৎ কেউ জানে না! তাই বাস্তবে চলে LRU — “যাকে সবচেয়ে বেশি সময় ধরে কেউ ছোঁয়নি, তাকে বের করে দিন” — অতীত দেখে ভবিষ্যতের আন্দাজ। LRU প্রমাণিত সেরা নয়, কিন্তু বেশিরভাগ বাস্তব কাজে কাছাকাছি, আর সস্তা। Bélády-র সেরা নিয়মটি তখন কাজে লাগে মাপকাঠি হিসেবে: “আমাদের LRU সেরা সম্ভাব্য ফলের কত কাছে?”

ব্যবসায়িক জগতেও একই: ডেলিভারি অ্যাপ প্রায়ই সবচেয়ে কাছের রাইডারকে অর্ডার দেয় — সহজ, দ্রুত, তবে সারাদিনের মোট হিসাবে সেরা নাও হতে পারে। বড় কোম্পানিগুলো তাই greedy দিয়ে শুরু করে, পরে প্রয়োজন হলে জটিল optimization যোগ করে।

মূল উপলব্ধি: বাস্তব প্রকৌশলে greedy দুই ভূমিকায় আসে — যেখানে প্রমাণ আছে সেখানে নিখুঁত সমাধান, আর যেখানে নেই সেখানে দ্রুত ও যথেষ্ট ভালো heuristic. কোনটি কোন ভূমিকায়, তা জানাই পেশাদারিত্ব।

প্র ০৫Sieve বাস্তবে এত দ্রুত কেন? আর ১০০ কোটি পর্যন্ত prime লাগলে কী করবেন?

কাগজে sieve-এর খরচ O(n log log n) — প্রায় n-এর সমান। কিন্তু বাস্তবের গতি শুধু কাজের সংখ্যায় নয়, মেমরির আচরণেও নির্ভর করে। Sieve-এর ভেতরের লুপ একটি array-তে নিয়মিত লাফে লেখে: কোনো ভাগ নেই, কোনো শাখা প্রায় নেই, শুধু একটি যোগ আর একটি লেখা। CPU এমন কাজ খুব দ্রুত করে। উল্টো দিকে প্রতিটি সংখ্যা আলাদা করে √n পর্যন্ত ভাগ করলে প্রতিটি ভাগ বেশ ধীর একটি নির্দেশ।

সমস্যা শুরু হয় n বড় হলে। ১০০ কোটি পর্যন্ত sieve-এ প্রতি সংখ্যায় একটি char রাখলে লাগে প্রায় ১ GB মেমরি। আর পর্ব ১৬-এর CPU cache মাত্র কয়েক MB — বড় prime-এর লাফগুলো প্রতিবার cache-এর বাইরে গিয়ে ধীর মূল মেমরি ছোঁয়। ফলে কাগজের হিসাবের চেয়ে অনেক ধীর চলে।

সমাধানের তিনটি ধাপ:

বিট ব্যবহার: প্রতি সংখ্যায় ১ byte নয়, ১ bit — মেমরি আট ভাগের এক ভাগ।
শুধু বিজোড়: ২ ছাড়া কোনো জোড় সংখ্যা prime নয়, তাই সেগুলো রাখারই দরকার নেই — আরও অর্ধেক।
Segmented sieve: প্রথমে √n (১০০ কোটির জন্য প্রায় ৩১,৬২৩) পর্যন্ত ছোট prime-গুলো বের করুন। তারপর পুরো পরিসরকে cache-এ আঁটে এমন ছোট টুকরোয় ভাগ করে প্রতিটি টুকরো ওই prime-গুলো দিয়ে ছাঁকুন। মেমরি লাগে শুধু একটি টুকরোর সমান, আর প্রায় সব কাজ হয় cache-এর ভেতরে।

Segmented sieve আরেকটি সুবিধা দেয়: আপনি চাইলে শুধু একটি পরিসর ছাঁকতে পারেন, যেমন 10¹² থেকে 10¹² + 10⁶ — শুরু থেকে সব না করেই। টুকরোগুলো আলাদা হওয়ায় একাধিক CPU core-এ একসাথেও চালানো যায়। এ ধরনের অপ্টিমাইজেশনের পর অত্যন্ত দ্রুত prime-sieve লাইব্রেরিগুলো একটি সাধারণ কম্পিউটারে কয়েক সেকেন্ডেরও কম সময়ে ১০০ কোটি পর্যন্ত সব prime গুনে ফেলে।

মূল উপলব্ধি: Big-O বলে কাজ কতটা বাড়ে; মেমরির নকশা বলে সেই কাজ আসলে কত দ্রুত হয়। আধুনিক কম্পিউটারে প্রায়ই “ডেটা কোথায় আছে” প্রশ্নটি “কতগুলো ধাপ” প্রশ্নের চেয়ে বেশি গুরুত্বপূর্ণ।

অনুশীলন

খাতা-কলম নিন — এগুলোর বেশিরভাগ হাতে হিসাব করার, কোড লেখার নয়।

Greedy-কে ঠকান: একটি দেশে কয়েন শুধু ১, ৭ আর ১০. সবচেয়ে ছোট কোন পরিমাণে “বড় কয়েন আগে” নিয়ম সবচেয়ে কম কয়েন দেয় না? Greedy কতটি দেয়, আর সেরা উত্তর কতটি?

সবচেয়ে ছোট পরিমাণ ১৪। Greedy নেয় ১০, তারপর বাকি ৪-এর জন্য চারটি ১ — মোট ৫টি কয়েন। অথচ ৭ + ৭ = ১৪, মাত্র ২টি। ১৩ পর্যন্ত greedy ঠিক থাকে; ১৫ আর ১৬-তেও ভুল করে। ছোট পরিমাণগুলো একে একে হাতে বা একটি ছোট DP দিয়ে যাচাই করলেই এমন counterexample বেরিয়ে আসে।
হাতে ইউক্লিড: gcd(১০৭১, ৪৬২) বের করুন, প্রতিটি ভাগশেষ লিখে। তারপর নিরাপদ ক্রমে lcm বের করুন।

1071 = 2 × 462 + 147 → (462, 147). 462 = 3 × 147 + 21 → (147, 21). 147 = 7 × 21 + 0 → (21, 0). তাই gcd = ২১, মাত্র তিনটি ভাগে। LCM: আগে 1071 / 21 = 51, তারপর 51 × 462 = ২৩,৫৬২। আগে গুণ করলে 1071 × 462 = 494802 হতো, তারপর ২১ দিয়ে ভাগ — এখানে int-এ আঁটে, কিন্তু আরও বড় সংখ্যায় এই মাঝের গুণফলই overflow করত।
সপ্তাহের ঘড়ি: আজ শুক্রবার। (ক) ১০০ দিন পর কী বার? (খ) ১০ দিন আগে কী বার ছিল? রবিবার = 0, সোমবার = 1 … শনিবার = 6 ধরে C-র সূত্রে হিসাব করুন — আর দেখুন সাধারণ % কোথায় ভুল করত।

শুক্রবার = 5. (ক) (5 + 100) % 7 = 105 % 7 = 0 → রবিবার। (খ) 5 − 10 = −5. C-তে -5 % 7 = -5 — এটি কোনো বারই নয়, আর array-র index হিসেবে ব্যবহার করলে array-র বাইরে চলে যেত। সংশোধিত সূত্র: ((−5 % 7) + 7) % 7 = (−5 + 7) % 7 = 2 → মঙ্গলবার। যাচাই: শুক্রবার থেকে ৭ দিন আগে আবার শুক্রবার, আরও ৩ দিন আগে মঙ্গলবার।
AI অডিট (ঐচ্ছিক কোড): যেকোনো AI-কে বলুন “C-তে দুটি int-এর lcm বের করার ফাংশন লেখো।” তারপর a = 100000, b = 99999 দিয়ে চালান। উত্তর 9999900000 আসে কি? না এলে কেন, আর কীভাবে ঠিক করবেন?

অনেক AI লেখে return a * b / gcd(a, b); আর ফেরত-টাইপ রাখে int. দুটি সমস্যা: (১) a * b = 9999900000, যা int-এর সীমা (2147483647) ছাড়িয়ে যায় — signed overflow, undefined behavior; বাস্তবে সাধারণত একটি অর্থহীন সংখ্যা আসে। (২) উত্তর নিজেই int-এ আঁটে না। ঠিক রূপ: ফেরত-টাইপ long long, আর return (long long)(a / gcd(a, b)) * b; — আগে ভাগ, তারপর বড় টাইপে গুণ। আর a = b = 0 দিলে gcd 0 হয়, তখন শূন্য দিয়ে ভাগ — এটিও দেখে নিন।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমSieve of Eratosthenes-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

২ থেকে n পর্যন্ত সব সংখ্যাকে “সম্ভাব্য prime” চিহ্ন দেওয়া
সবচেয়ে ছোট না-কাটা সংখ্যা p নেওয়া — এটি prime
p × p থেকে শুরু করে p-এর সব গুণিতক কেটে দেওয়া
পরের না-কাটা সংখ্যায় যাওয়া, যতক্ষণ p × p ≤ n
যেগুলো না-কাটা রইল, সেগুলোই prime হিসেবে ছাপা

একটি রুমে সবচেয়ে বেশি সংখ্যক অনুষ্ঠান রাখতে greedy কোন মাপকাঠিতে সাজাবে?

সবচেয়ে আগে শুরু হওয়া অনুষ্ঠান আগে
সবচেয়ে ছোট অনুষ্ঠান আগে
সবচেয়ে আগে শেষ হওয়া অনুষ্ঠান আগে
সবচেয়ে লম্বা অনুষ্ঠান আগে

কয়েন {১, ৩, ৪} দিয়ে ৬ বানাতে “বড় কয়েন আগে” greedy কতটি কয়েন নেয়?

২টি
৩টি
৬টি
বানাতেই পারবে না

ইউক্লিডের পদ্ধতিতে gcd(48, 18) — কোন ক্রমটি সঠিক?

(48, 18) → (18, 6) → (6, 0) → 6
(48, 18) → (18, 12) → (12, 0) → 12
(48, 18) → (18, 2) → (2, 0) → 2
(48, 18) → (18, 12) → (12, 6) → (6, 0) → 6

Sieve-এ prime p-এর গুণিতক কাটা কেন 2p থেকে নয়, p × p থেকে শুরু হয়?

কারণ p × p-এর চেয়ে ছোট সব গুণিতক আগেই কোনো ছোট prime-এর ধাপে কাটা পড়েছে
কারণ 2p থেকে শুরু করলে ভুল উত্তর আসে
কারণ 2p array-র বাইরে চলে যায়
কারণ p × p সবসময় prime

C99 বা তার পরের C-তে -8 % 3-এর মান কত?

1
-2
2
Compile error হবে

modpow দিয়ে 2^1000000 mod p হিসাব করতে লুপ মোটামুটি কতবার ঘুরবে?

প্রায় ২০ বার
প্রায় ১০ লাখ বার
প্রায় ১,০০০ বার
মাত্র ১ বার

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

Greedy প্রতিটি ধাপে এখনকার সেরাটা নেয়, পেছনে ফেরে না। Activity selection-এ “যেটা আগে শেষ, সেটা আগে” সবসময় সেরা — exchange argument তার প্রমাণ।
একটি counterexample-ই greedy-কে বাতিল করে: {১, ৩, ৪}-এ ৬. তখন DP; আর সন্দেহ হলে ছোট ইনপুটে brute force দিয়ে মিলিয়ে দেখুন।
gcd(a, b) = gcd(b, a % b), b = 0 হলে a. LCM লিখুন a / gcd * b — আগে ভাগ, পরে গুণ।
Sieve: p × p থেকে কাটা শুরু, p × p > n হলে থামা, array-র আকার n + 1. খরচ O(n log log n).
প্রতি ধাপে % m, গুণে long long, ঋণাত্মকে ((x % m) + m) % m. modpow O(log n), আর prime m-এ inverse = a^m−2.

পরের পর্বে: এতদিন যা শিখলেন — sorting, searching, graph, DP, greedy, নাম্বার থিওরি — সব একসাথে কাজে লাগবে কনটেস্টে। দ্রুত ইনপুট-আউটপুট, সময়ের সীমা দেখে অ্যালগরিদম বাছাই, আর brute force দিয়ে নিজের কোড যাচাইয়ের কৌশল দেখব।

Greedy ও নাম্বার থিওরি — এখনই সেরাটা বাছাই, আর সংখ্যার গোপন নিয়ম

এই পর্বে যা শিখবেন

১ · Greedy — এই মুহূর্তের সেরা পছন্দ

২ · একটি সেমিনার রুম, অনেক অনুষ্ঠান

কেন “আগে শেষ” কখনো ঠকায় না — বদলে দেওয়ার যুক্তি

৩ · যখন greedy ঠকায় — টাকার নোট বনাম অদ্ভুত কয়েন

🤑 Greedy-র উত্তর

✅ সেরা উত্তর

৪ · প্রোগ্রামারের নাম্বার থিওরি — ভাগ, ভাগশেষ আর prime

একটি সংখ্যা prime কি না — √n পর্যন্ত দেখলেই যথেষ্ট

৫ · GCD — ইউক্লিডের প্রায় ২,৩০০ বছরের পুরোনো অ্যালগরিদম

LCM — গুণের আগে ভাগ

৬ · Sieve of Eratosthenes — prime ছেঁকে তোলা

৭ · Modular arithmetic — ঘড়ির অঙ্ক

তিনটি সোনালি নিয়ম

কনটেস্টে কেন “answer modulo 1,000,000,007”?

C-র `%` আর ঋণাত্মক সংখ্যা

৮ · দ্রুত ঘাত — বারবার বর্গ, দরকার হলে গুণ

Modular inverse — mod-এর জগতে “ভাগ”

৯ · বাস্তবে নাম্বার থিওরি — RSA, Diffie–Hellman আর চেকসাম

🔐 RSA (১৯৭৭)

🤝 Diffie–Hellman (১৯৭৬)

চেকসাম — ছোট ভুল ধরার ভাগশেষ

১০ · AI-এর যুগে greedy ও নাম্বার থিওরি — যা যাচাই করবেন

AI-এর দেওয়া greedy বা নাম্বার থিওরির কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

অনুশীলন

নিজেকে যাচাই করুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বে যা শিখবেন

১ · Greedy — এই মুহূর্তের সেরা পছন্দ

২ · একটি সেমিনার রুম, অনেক অনুষ্ঠান

কেন “আগে শেষ” কখনো ঠকায় না — বদলে দেওয়ার যুক্তি

৩ · যখন greedy ঠকায় — টাকার নোট বনাম অদ্ভুত কয়েন

🤑 Greedy-র উত্তর

✅ সেরা উত্তর

৪ · প্রোগ্রামারের নাম্বার থিওরি — ভাগ, ভাগশেষ আর prime

একটি সংখ্যা prime কি না — √n পর্যন্ত দেখলেই যথেষ্ট

৫ · GCD — ইউক্লিডের প্রায় ২,৩০০ বছরের পুরোনো অ্যালগরিদম

LCM — গুণের আগে ভাগ

৬ · Sieve of Eratosthenes — prime ছেঁকে তোলা

৭ · Modular arithmetic — ঘড়ির অঙ্ক

তিনটি সোনালি নিয়ম

কনটেস্টে কেন “answer modulo 1,000,000,007”?

C-র % আর ঋণাত্মক সংখ্যা

৮ · দ্রুত ঘাত — বারবার বর্গ, দরকার হলে গুণ

Modular inverse — mod-এর জগতে “ভাগ”

৯ · বাস্তবে নাম্বার থিওরি — RSA, Diffie–Hellman আর চেকসাম

🔐 RSA (১৯৭৭)

🤝 Diffie–Hellman (১৯৭৬)

চেকসাম — ছোট ভুল ধরার ভাগশেষ

১০ · AI-এর যুগে greedy ও নাম্বার থিওরি — যা যাচাই করবেন

AI-এর দেওয়া greedy বা নাম্বার থিওরির কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

অনুশীলন

নিজেকে যাচাই করুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

C-র `%` আর ঋণাত্মক সংখ্যা