Euler’s Phi Function [ Number Theory ]

0

আজকে আমরা জানবো অয়লারের টশিয়েন্ট ফাংশন (Euler’s Phi Function) সম্পর্কে । যাকে প্রকাশ করা হয় φ(n) দিয়ে । আমরা φ(n)=x বলতে বুঝি 1 থেকে n অবধী x সংখ্যক সংখ্যা আছে যে সংখ্যা গুলো n এর সহমৌলিক (coprime) অর্থাৎ 1 থেকে n এর মধ্যে x সংখ্যক সংখ্যা আছে যাদের সাথে n এর GCD হবে 1.
যেমনঃ GCD(7,11)=1 তাই এরা সহমৌলিক (coprime)।

উদাহরণঃ φ(24) = 8

কারণ ->
GCD(1,24)=1, GCD(2,24)=2 , GCD(3,24)=3, GCD(4,24)=4 , GCD(5,24)=1, GCD(6,24)= 6 , GCD(7,24)=1, GCD(8,24)=8 ,
GCD(9,24)=3,GCD(10,24)=2, GCD(11,24)=1,GCD(12,24)=12,

GCD(13,24)=1, GCD(14,24)=2 , GCD(15,24)=3, GCD(16,24)=8 , GCD(17,24)=1, GCD(18,24)= 6 , GCD(19,24)=1, GCD(20,24)=4 ,
GCD(21,24)=3, GCD(22,24)=2, GCD(23,24)=1 , GCD(24,24)=24

এখানে মাত্র 8 টি সংখ্যা 24 এর সাথে কো-প্রাইম হিসেবে আছে তাই আমাদের φ(24) = 8 . একে অন্য ভাষায় বলা হয় number of totatives of n.

উপরের উদাহরণে একটা বেপার খেয়াল করি 12 জন্য কারা কারা বাদ পড়লো? 12 যাদের যাদের multiples হিসেবে আছে তারাই শুধুমাত্র বাদ পড়েছে তাই না? যেমনঃ 2, 3 , 4 , 6, 12 এর multiples 12 তারা বাদ পড়েছে আর অতিরিক্ত বাদ পড়েছে 8 , 9 এবং 10 কেননা 8 , 10 দুইটা 2 এর multiples এবং 9 হচ্ছে 3 এর multiple.তাহলে আমরা বলতে পারি এখানে number of totatives of n is 4 where n=24.

Totient Function এর Brute Force বা কামলা কোডটি এখানেই

এখন আমরা একটা বেপার ভালোভাবে খেয়াল করলে দেখবো প্রতিটা প্রাইম নাম্বারের totative অর্থাৎ φ এর মান অবশ্যই ওই নাম্বার থেকে 1 কম । তাহলে,
φ(n) = n-1

যেখানে n একটি প্রাইম নাম্বার ।

উদাহরণঃ

n = 7 এর জন্যঃ

GCD(1,7)=1
GCD(2,7)=1
GCD(3,7)=1
GCD(4,7)=1
GCD(5,7)=1
GCD(6,7)=1
এবং
GCD(7,7)=7

φ(7) = 6

এভাবে সকল প্রাইম নাম্বারের জন্য φ(n) = n-1 সমীকরণটি সত্যি । কেন তা হয়তো বুঝতে আর দেরি নেই সবার 🤓

এখন আসি যখন n প্রাইম সংখ্যা হবে না তখন আমাদের সমীকরণটি কেমন হবে। ধরি আমাদের n একটি যৌগিক বা composite নাম্বার । এবং আমরা সবাই জানি যেকোন যৌগিক বা composite নাম্বারকে প্রাইম নাম্বারের গুনফল আকারে প্রকাশ করা যায় ( যেমনঃ 10 কে আমরা লিখতে পারি 2¹*5¹ এভাবে , 24 কে আমরা লিখতে পারি 2³ * 3¹ এভাবে)

ধরি ,

m=p^k

(এখানে m আমাদের composite নাম্বার এবং p যেকোন প্রাইম নাম্বার)

এখন যে নাম্বার গুলোর m এর সাথে common factor হিসেবে থাকবে সেগুলো অবশ্যই p এর multiples হবে তাই না?

তাহলে আমরা বলতে পারি p এর multiples গুলো হচ্ছে এমনঃ

1

এখানে m এর সাথে common factors এর পরিমান হবে অবশ্যইঃ

2

এখন তুমি বলবা আমি শুধু বলেই যাচ্ছি কিন্তু প্রমান দিচ্ছি না 😕। আসলে বেপারটা খুব সহজ চলো আবারও একটা উদাহরণ দেখিঃ

ধরি, m=2⁴
তাহলে m=2⁴=16 এর সাথে যে নাম্বার গুলোর common factors আছে সেগুলো 2, 2*2, 3*2 , 4*2 , 5*2 , 6*2, 2*7, 8*2 এর পরের গুলো ধরা হচ্ছে কেননা তা m=16 অতিক্রম করছে।
এখানে মোট common factors গুলোর পরিমান 2^(4–1)=8 তাই না? সব ঠিকঠাক 😛

তাহলে এখন মোট সংখ্যা থেকে common factors এর সংখ্যা বাদ দিলেই পেয়ে যাবো আমাদের কাঙ্ক্ষিত φ(m) এর মান ।

তাহলে ,

3

এই সমীকরণকে আমরা ভেংগে লিখতে পারি,

4

এখন যে সমীকরণটি আমরা পেলাম সেটা হলো যদি কোন নাম্বার একটি মাত্র প্রাইমের গুনফল আকারে থাকে সেটার জন্য । এখন আমাদের নাম্বারটি একধিক সংখ্যক প্রাইমের গুণফল আকারে প্রকাশ করতে হতে পারে । তাই সমীকরণটিকে generalized করতে হবে যাতে করে সব ক্ষেত্রে ওই সমীকরণ থেকে সঠিক সমাধান পেতে পারি।

এখন আমরা যদি φ(n) এর মান বের করতে চাই যেখানে n হচ্ছেঃ

5

এখানে p1 < p2 < … < pr হচ্ছে প্রাইম নাম্বার এবং ki ≥ 1 যা প্রাইমের ঘাত ।

তাহলে φ(n) এর জন্য সমীকরণটি হচ্ছে এমনঃ

6

বা,

7

এখানে p হচ্ছে মৌলিক সংখ্যা আর p|n মানে হচ্ছে সেইসব মৌলিক সংখ্যা যারা n কে নি:শেষে ভাগ করতে পারে। যেমন ধরো যখন আমরা লিখি a|b, এর মানে হচ্ছে a নি:শেষে ভাগ করতে পারে b কে। মানে, a হচ্ছে b এর ডিভিজর।

যা অয়লারের প্রোডাক্ট ফরমুলা নামে পরিচিত ।

উদাহরণঃ

8

Euler’s Phi Coding:

আমরা Theorem এ দেখলা প্রতিবার প্রতিটা প্রাইমের জন্য যে পরিমান common factors বা multiples আছে তা মূল সংখ্যা থেকে প্রতিবার বিয়োগ করতে হবে ।

তাহলে 1 থেকে n এর মধ্যে কোন সংখ্যা p এর common factors বা multiples এর পরিমান জানা যায় কিভাবে?

factor = n/p [যেখানে n হচ্ছে আমাদের প্রদত্ত নাম্বার যার Totient ভ্যালু বার করতে চাচ্ছি এবং p হচ্ছে প্রাইম নাম্বার গুলোর একটি ]

যেমনঃ

1 থেকে 10 এর মধ্যে 2 এর multiples সংখ্যা হচ্ছে 10/2=5 (যেমনঃ 2, 4, 6, 8, 10)

1 থেকে 10 এর মধ্যে 3 এর multiples সংখ্যা হচ্ছে 10/3=3 (যেমনঃ 3, 6, 9)

এখন আমরা ফিরে যাবো আমাদের φ(24) এর কাছে এবং দেখবো কিভাবে এটার উত্তর আমরা পেতে পারি।

24 কে প্রাইমের গুণফল আকারে লিখা যায় এভাবে 24 = (2³ * 3¹)

φ(24) এর সর্বোচ্চ মান হতে পারে 24 তাই এই 24 কে আমরা res এ এসাইন করবো।

res=24

24 এ প্রাইম সংখ্যা দুইটা → 2 এবং 3.

1 থেকে 24 এর মধ্যে 2-এর multiples বা common factors আছে কয়টি? উত্তরঃ 24/2=12টি এবং সেই সংখ্যা গুলো বাদ হয়ে যাবে (যা উপরে আমরা theorem এ জেনেছি) . তাহলেঃ

res=24–12=12

এখন n =24 কে 2 দিয়ে যতক্ষন ভাগ করা যায় করবো । (এখনে ভাগ করা যায় বলতে বোঝানো হয়েছে ভাগ করার ফলে ভাগশেষ শূন্য হওয়াকে)

n=24/2=12

n=12/2=6

n=6/2=3

এবার, 1 থেকে 12 এর মধ্যে 3-এর multiples আছে কয়টি? উত্তরঃ 12/3=4টি এবং সেই সংখ্যা গুলো বাদ হয়ে যাবে।

res=12–4=8

n=3 কে 3দিয়ে যতক্ষন ভাগ করা যায় করবো ।

n=3/3=1

এখানে n=1 হয়ে গেছে তাই কাজ এখানেই খতম । 😎

অবশেষে আমাদের res=8 যা আমাদের কাঙ্ক্ষিত উত্তর ।

কোন কনফিউশন থাকলে কোডটা দেখো আশাকরি পরিস্কার হয়ে যাবে।

কোডঃ

আরও একটু Efficient Phi :

এই পদ্ধতি ঠিক তখনই কাজ করবে যখন আমরা এটা জানি যে আমাদের অনেকবার টোশিয়েন্ট ফাংশনকে কল করা লাগবে। তখন আমরা টোশিয়েন্ট ফাংশনকে সিভের মত করে ইমপ্লিমেন্ট করবো। ছোট থেকে বড় প্রতিটা প্রাইমের জন্য ওই ইনডেক্সের টোশিয়েন্ট ভ্যালু আপডেট করবো।

কোডটা দেখুনঃ

এই ছিলো আমাদের Euler’s Totient Phi Function. এই ফাংশটির অনেক এপ্লিকেশন আছে । হয়তো তা নিয়ে সামনে কোন একদিন লিখবো । আজ ছোট্ট একটি ট্রিক্সস বোনাস হিসেবে দিয়ে আজ শেষ করবো 😄। তা হচ্ছেঃ

9

তার মানে হচ্ছে যদি একটা প্রাইমের দুই বা তার অধিক ঘাত হিসেবে কোন সংখ্যা প্রকাশ করা যায় তাহলে তার জন্য Totient Phi আমরা খুব সহজেই বের করে ফেলতে পারি।

যাওয়ার আগে শেষ উদাহরণঃ

φ(343)=φ(7³)

=> 7²*φ(7)

=>7² * (7–1) = 294

উত্তরটা মিলিয়ে দেখতে পারো ।

হ্যাপি কোডিং 😊

Advertisements

Segmented Sieve [ Number Theory ]

0

আজ আমরা Segmented Sieve সম্পর্কে জানবো। Segmented Sieve এর আরেক নাম Segmented Sieve of Eratosthenes । সেগমেন্টেড সিভ (Segmented Sieve) সম্পর্কে জানতে হলে আমাদের আগে জানতে হবে Sieve এলগোরিদম সম্পর্কে যা “Sieve of Eratosthenes” নামে পরিচিত। Sieve of Eratosthenes নিয়ে অনেক ভালো ভালো ব্লগ বাংলায় আছে তাই এটা নিয়ে নতুন করে কিছু লিখবো না। আমরা সরাসরি চলে যাবো Segmented Sieve এ।

Segmented Sieve: এলগরিদমের নাম অনুসারেই নির্দিষ্ট সেগমেন্ট বা রেঞ্জ এর মধ্যে প্রাইম নাম্বার জেনারেট করার জন্য খুব কার্যকরী একটা এলগরিদম এই Segmented Sieve.

সমস্যাঃ যদি আমাদের L এবং R এর একটি রেঞ্জ দেওয়া থাকে এবং বলা হয় L এবং R এর মধ্যবর্তী সকল প্রাইম নাম্বার প্রিন্ট করতে তখন আমরা কি করব? (যেখানে Constraints হচ্ছে 1<=L<=R<=10¹⁰, R-L <= 10⁵)
যেমন ধরুন আপনাকে কেউ প্রশ্ন করল “29 থেকে 700 পর্যন্ত কোন কোন নাম্বার প্রাইম আছে?” তা প্রিন্ট করো।

আমরা তো “Sieve of Eratosthenes” এর মাধ্যমে Global Array ব্যাবহার করে সর্বোচ্চ 10⁸ পর্যন্ত প্রাইম নাম্বার জেনারেট করতে পারবো।কিন্তু এখানে আমরা 10¹⁰ সাইজের এতো বড় Array তো Declare করতে পারবো না 🤔। তাহলে এখন আমাদের কি হবে? 😥

আমরা Sieve এলগোরিদম এর সাথে আমাদের কিছু Observations কে কাজে লাগিয়ে Segmented Sieve টা করে ফেলবো।

Lets বেগুন 😂

★★ Sieve এলগোরিদমে আমরা যদি 100 অবধি প্রাইম নাম্বার জেনারেট করতে চাইতাম তাহলে কি করেছিলাম?

sqrt(100)= 10 অবধী লুপ চালিয়ে এক একটা Element কে ধরে তার Multiples গুলোকে কেটে দিয়ে ছিলাম তাই না?

যেমনঃ প্রথমে 2 কে ধরে তার Multiples 2,4,6…. সবগুলো কেটেছি।

তারপর 3 কে ধরেছি তার Multiples 6,9,12,15…. সবগুলো কেটেছি। এভাবে ১০ অবধী সকল নাম্বারকে ধরে তার Multiples গুলো কাটার পর আমাদের কাছে অবশিষ্ট যে নাম্বারগুলো ছিলা সেগুলো Prime. তাই না?

এখানে আমরা ঠিক তাই করবো। 10¹⁰ অবধী প্রাইম নাম্বার পেতে হলে আমাদের sqrt(10¹⁰)= 10⁵ অবধী সবগুলো প্রাইম নাম্বার জেনারেট করে নিবো।

তারপর আমরা প্রতিটা প্রাইম নাম্বারকে ধরবো এবং আমাদের দেওয়া সেগমেন্ট বা রেঞ্জের মধ্যে ওই প্রাইমের Multiples গুলো কাটবো।

যেমনঃ ধরি আমাদের L=29 থেকে R=700 অবধী প্রাইম নাম্বার জেনারেট করতে হবে।

তাহলে sqrt(700)= 26.4575 ~ 27 অবধী প্রাইম নাম্বার Sieve এর মাধ্যমে জেনারেট করে নিবো৷
1 থেকে 27 এর প্রাইম নাম্বার হচ্ছে 2,3,5,7,11,13,17,19,23।

এখন আমরা 2 কে ধরবো এবং আমাদের সেগমেন্টের মধ্যে 2 এর জন্য composite নাম্বার মার্ক করবো বা কেটে দিবো। একই ভাবে 3,5,7 ইত্যাদি সকল প্রাইমকে দিয়ে আমাদের সেগমেন্ট বা রেঞ্জের মধ্যে ওই প্রাইমের জন্য Composite নাম্বার কেটে দিবো। তাহলে ফাইনালি আমাদের সেগমেন্টে অবশিষ্ট যে নাম্বারগুলো থাকবে তা অবশ্যই প্রাইম ☺।

  • *এখন কথা হচ্ছে সেগমেন্টের ভিতরে বিভিন্ন প্রাইমের জন্য প্রথম Composite নাম্বার কোনটা যা আমরা প্রথমে মার্ক করবো বা কাটবো?

যেমনঃ

আমাদের হাতে জেনারেট করা ,১ম প্রাইম 2 এর জন্য আমরা কাটা শুরু করবো কত থেকে? অবশ্যই 4 থেকে নয়, কেননা এইগুলা তো Sieve এর মাধ্যমে আগেই কাটা হয়ে গেছে। তাই আমরা এখন শুধুমাত্র সেগমেন্টের ভিতরের Composite নাম্বারগুলো কাটবো।

প্রতিটা প্রাইম নাম্বারের জন্য যে নাম্বারটি আমরা প্রথমে কাটবো (যা আমরা base ধরলাম) তা পাওয়ার সুন্দর একটা ফরমুলা আছে। যা নিম্নে দিলাম।

base = curPrime*curPrime;

(এখানে curPrime বলতে আমি বুঝিয়েছি 2, 3,5… ইত্যাদি প্রাইম নাম্বারগুলো যা আমরা আগেই Sieve এর মাধ্যমে জেনারেট করেছি)

এখন কথা হচ্ছে base এর মান যদি আমাদের সেগমেন্টের শুরু L থেকে ছোট হয়, তাহলে শুধু কারেন্ট প্রাইম এর বর্গ করলে হবে না। যেমন ২ এর বর্গ ৪, কিন্তু আমাদের L=29 যেটা এখনও অনেক দূরে। তখন base বা রেঞ্জের মধ্যে প্রথম Composite খুজে পাবো ছোট একটা কন্ডিশনের মাধ্যমে।

if(base < L)
base = ( ( L + curPrime — 1 ) / curPrime ) * curPrime;

প্রশ্নঃ কিভাবে এই ফর্মুলা আসলো?

উত্তরঃ

ধরুন আপনাকে জিজ্ঞেস করা হলো –
“19 এর সমান বা ছোট কোন সংখ্যাটা 3 দ্বারা নিঃশেষে বিভাজ্য?” [ Ans: 18 ]
“19 এর সমান বা বড় কোন সংখ্যাটা 3 দ্বারা নিঃশেষে বিভাজ্য?” [ Ans : 21 ]
কিভাবে পেলাম?
19/3 এর ভাগফল 6, এটাকে আবার 3 দিয়ে গুন করলে 18। এটা আমাদের ১ম প্রশ্নের উত্তর।
19/3 এর ভাগফল 6, এর সাথে অতিরিক্ত 1 + করে পাই (7/7)*3 = 21 যা আমাদের ২য় প্রশ্নের উত্তর।

১ম উপায় ঠিক ভাবে কাজ করলেও ২য় টি ভুল উত্তর দিবে যদি প্রশ্নে 19 এর বদলে 21 দেয়া থাকে।
মানে যদি হর দ্বারা লব নিঃশেষে বিভাজ্য হয় তখন ভুল উত্তর আসবে।
21 এর জন্য ১ম উত্তর আসবে 21 [ যা ঠিক ] , কিন্তু ২য় উত্তর আসবে 24 [ যা ভুল, সঠিক উত্তর 21 ]
তাহলে কি করা যায়?
আমরা আমাদের ২য় ফর্মুলা একটু এদিক ওদিক করব যেন সেটা সবসময় ঠিক উত্তর দিতে পারে।
আমরা 21 ( লব ) থেকে 1 বিয়োগ করব আর 3 ( হর ) যোগ করে নিব।
মানে ( 21–1 +3 ) = 23।
23/3 এর ভাগফল (7/7)*3 = 21 যা আমাদের উত্তর।
এটাই উপরের ফর্মুলার রহস্য!

এখন দুইটা উদাহরণ দেখা যাকঃ

প্রথম প্রাইম 2 এর জন্য রেঞ্জের ভিতর প্রথম Composite মার্ক হবে এভাবে,

base = 2*2;

যা আমাদের সিগমেন্টের L = 29 থেকে ছোট তাই

base= ((29+2–1)/2)=15*2=30

তাহলে প্রথম Composite কাটবো 30 এবং তারপর R অবধি 2 এর সকল Multiplesকাটবো।

তাহলে 2 এর জন্য রেঞ্জের ভিতরে কাটা যাবে বা Composite মার্ক হবে 30,34,36,38…. এভাবে R=700 অবধী।

২য় প্রাইম 3 এর জন্য একই ভাবে কাটা যাবে 33,36,39… এভাবেই রেঞ্জ R=700 অবধী।

তাহলে একই ভাবে sqrt(700)= 26.4575 ~ 27 এর আগে যত প্রাইম আছে সবগুলোর জন্য Composites কাটবো বা মার্ক করবো।

★★ এখন আসি আমরা Array Deceleration এ। আমাদের সেগমেন্ট বা রেঞ্জ এর ভ্যালু R সর্বোচ্চ 10¹⁰ হতে পারে। তাহলে আমরা এতো বড় সাইজের Array কিভাবে Declare করবো? এতো বড় সাইজের Array Declare করা তো অসম্ভব,তাহলে উপায়?😧😢

আসলে আমাদের এতো বড় সাইজের Array নিতেই হবে না। কেননা, আমাদের Constraints এ বলা আছে R-L = 10⁵ এবং আমরা শুধুমাত্র 10⁵ সাইজের Array Declare করলেই চলবে। শুধুমাত্র Index গুলো ম্যাপ করবো সিম্পল 😋।

যেমনঃ
আমাদের উদাহরণ অনুযায়ী যদি L=29 এবং R=700 হয়, তাহলে Array নিবো R-L সাইজের।

int isPrime [ R — L + 1 ];

এখানে আমরা,

isPrime[0] মানে বুঝবো 29
isPrime[1] মানে বুঝবো 30
isPrime[2] মানে বুঝবো 31
.
.
.
.
isPrime[R-L] মানে বুঝবো 700

এবং যদি আমাদের প্রাইম নাম্বার প্রিন্ট করতে বলা হয় তখন L+index প্রিন্ট করে দিবো।
এভাবেঃ

if ( isPrime[i] == true )
cout << L+i << endl;

যেমনঃ

31 মানে আমাদের কাছে isPrime[2]. প্রোগ্রামার শেষে আমরা isPrime[2]=trueপাবো, কেননা 31 একটি প্রাইম নাম্বার।তাহলে L+index = 31 হয়।

একটা কথা মাথায় রাখতে হবে আমাদের যদি L=1 তাহলে isPrime[0]=false হবে, কেননা প্রাইম নাম্বার না।

এখন ঝামেলা মনে হলে, লিখাটা আরেকবার পড়ো। এবং আশাকরি নিচের কোডের Implementation দেখলে ক্লিয়ার হয়ে যাবে।
[ সাথে ১টা স্প্রাইট রাখতে পারেন 😉 ]

কোডঃ 

 

সম্পুর্ন কোডের লিংকঃ Segmented Sieve Full Code

একটু ভেংগে লিখতে গিয়ে হয়তো লিখাটা একটু বড় হয়ে গেছে। কোথাও কোন প্রশ্ন থাকলে অবশ্যই জানাবেন।

আজ এই পর্যন্তই রইলো । সামনে কোন একদিন অন্যকোন টপিক্স নিয়ে লিখবো আশা করি ।

★★ আমার লিখার Inspirations পেয়েছি Md Shahidul Islam ভাই এবং Shakil Ahmed ভাই এর কাছে থেকে।

Happy Coding 🙂

 

Divisibility Rule || UVa 11344 – The Huge One

0
PROBLEM : UVa 11344 The Huge One
Descriptions : প্রবলেমে বলা হয়েছে, তোমাকে একটা নাম্বার M দিবে এবং একটি সেট S দিবে, যেখনে S এর ভিতর 1–12 পর্যন্ত কিছু সংখ্যা থাকবে৷ তোমাকে বলতে হবে সেট S এ যে সংখ্যাগুলো দেওয়া আছে তাদের সবগুলো নাম্বার দিয়ে উপরের M কে ভাগ করা যায় কিনা (এখনে ভাগ করা যাওয়া মানে হচ্ছে ভাগশেষ শূন্য হবে কিনা বোঝানো হয়েছে)। যদি সেট S এর সব গুলো সংখ্যা দিয়ে ভাগ যায় তাহলে প্রিন্ট করতে হবে M — Wonderful. (M এখানে হচ্ছে প্রদত্ত নাম্বার) অন্যথায় M — Simple. প্রিন্ট করতে হবে।
এই ছিলো প্রবলেম, এখন সমস্যা হচ্ছে Constent এ দেওয়া আছে 0<=M<=10¹⁰⁰⁰ 😥.
যেহেতু আমি বিগ নাম্বার দেখলেই ভয় পাই, সেই সুবাধে মাথায় চক্কর দিলো 😓
যেহেতু আমি বিগেনার প্রোগ্রামার, ভাবলাম মোড করে না হয় চেক করবো, কিন্তু এতো বড় নাম্বার store করবো কিভাবে।
দুইদিন ঝিমানোর পরে দুইটা উপায় পেলাম .
আজ সেই দুইটা এপ্রোজ নিয়েই কথা হবে .
Lets বেগুন 😛
Approach One :
(অনেক বড় নাম্বার হওয়া M আমাদের string এ নিতে হবে)
প্রথম উপায়টা একদম সহজ, Modular Arithmetic Approach.
Modular Arithmetic নিয়ে ডিটেইল আলোচনা করবো না, কেননা এ নিয়ে বাংলা এবং ইংরেজিতে অনেক ভালো ভালো লেখা আছে।
শাফায়াত ভাইতের সোনার টুকরার লেখাটা পড়ে আসতে পারোঃ  মডুলার অ্যারিথমেটিক
এই প্রবলেম সলিউশন এর জন্য সাধারন সমিকরণ টা হবে এমনঃ  a*10%m=((a%m)*10)%m
এই approach টি নাম্বারের প্রথম থেকে (বাম পাশ থেকে) শেষ অবধী লুপের মাধ্যমে প্রতিটা ডিজিটের জন্য এপ্লাই হবে। এবং সেটা অবশ্যই সেট S এর প্রতিটা নাম্বারের জন্য৷
সমিকরণে a দিয়ে বোঝানো হয়ে বামদিক থেকে প্রতিটা ডিজিট এবং m হচ্ছে সেটের প্রত্যেক এলিমেন্ট, যেগুলো দিয়ে ভাগ করে করে চেক করতে হবে।
আশাকরি, শাফায়াত ভাই এর ব্লগ পড়ে থাকলে এবং উপরুক্ত সমিকরণটি কেন কাজ করছে তা বুঝতে পেরেছো। যদি তবুও না বুঝে থাকো তাহলে আবার পড় এবং খাতা কলমে একটু দাগাদাগি করো। 🙂
এখনো পাড়ছো না? 😕 নিচের সলিউশনটা দেখো এবং বুঝর চেষ্টা করো।

Solution One Code :

[বিঃদ্রঃ কোড কপি পেষ্ট করে শুধুমাত্র Accepted কোডের সংখ্যা না বাড়িয়ে,কোডটি বুঝে নিজের মেধাকে বাড়াও ]
Approach Two :
এখন আসি আমার পছন্দের এবং মজার approach😍.
এটাও খুব সহজ একটা approach 😋.
স্বভাবতই, আমরা string এ ইনপুট নিবো।
এখন একটা বেপার খেয়াল করা যাক। আমাদের যে নাম্বর গুলো দিয়ে প্রতিবার ভাগ যায় কিনা চেক করতে হচ্ছে তা কিন্তু ফিক্সড যা অবশ্যই 1 থেকে 12 এর মধ্যেই।
এখন আমরা যদি (M) কোন সংখ্যা দেখে চট করে বলে দিতে পারি যে, এই সংখ্যাটি কি আমাদের সেটের সংখ্যা দিয়ে ভাগ যায় কিনা তাহলেই তো হয়ে গেলো। ভাগ করে দেখার তো দরকার নাই তাই না?
হ্যা, এবং আমরা সেটাই করবো। আমরা প্রথম সহজ কিছু উপায় শিখবো যাতে করে বলতে পারি কোনো সংখ্যা কোন কোন সংখ্যা দিয়ে ভাগ যায় কি না। তাহলেই তো আমরা এই প্রবলেমটা থেকে হাত ছেড়ে বাচতে পরি।
তাহলে আমরা 1 থেকে 12 এর সবগুলো নাম্বারের জন্য Divisibility Rules গুলো দেখবোঃ
1 এর জন্য রুলঃ 1 তো বেচরা নাম্বার 😛 এটা দিয়ে দুনিয়ার সব নাম্বার কে ভাগ করা যায়।
2 এর জন্য রুলঃ আমরা জানি, 2 শুধু মাত্র জোড় সংখ্যকে ভাগ করতে সক্ষম। এবং এটাও জানি, কোন সংখ্যার শেষের ডিজিটি জোড় মানে পুরো সংখ্যটি জোড়।
যেমনঃ 1678936 এই সংখ্যা দিয়ে বিভাজ্য কারন এর শেষের 6 জোড় সংখ্যা যা দুই দিয়ে ভাগ যায়।
3 এর জন্য রুলঃ কোন নাম্বারের প্রতিটা ডিজিটের যোগফল যদি 3 দিয়ে ভাগ যায়। তাহলে সেই সংখ্যাটি অবধ্যই ৩দিয়ে বিভাজ্য 🙂
যেমনঃ 123639 এই সংখ্যাটির ডিজিট গুলোর যোগফলঃ 1+2+3+6+3+9 = 24 যা 3 (24%3=8) দিয়ে বিভাজ্য । তাই পুরো সংখ্যাটি 3 দিয়ে বিভাজ্য।
4 এর জন্য রুলঃ কোন সংখ্যার শেষের দুইটি সংখ্যা যদি 4 দিয়ে বিভাজ্য হয় তাহলে সেই পুরো সংখ্যাটি 4 দ্বারা বিভাজ্য হবে।
যেমনঃ 1226732432 এখনে শেষে দুইটি সংখ্যা 32 যা 4 (32÷4=8) দ্বারা বিভাজ্য।
5 এর জন্য রুলঃ
কোন সংখ্যার শেষের ডিজিট 0 অথবা 5 থাকলে সেই সংখ্যাটি অবশ্যই 5 দ্বারা বিভাজ্য হবে।
যেমনঃ 15727775 এবং 165378390
6 এর জন্য রুলঃ কোন সংখ্যা যদি 2 দ্বারা এবং 3 দ্বারা যৌথ ভাবে বিভাজ্য হয়, তাহলে ওই সংখ্যাটি অবশ্যই 6 দ্বারা বিভাজ্য হবে।
যেমনঃ 72665412 সংখ্যাটি উপরের রুল অনুযায়ী 3 এং 2 উভয় সংখ্যা দ্বারা বিভাজ্য তাই সংখ্যাটি 6 দ্বারা অবশ্যই বিভাজ্য।
7 এর জন্য রুলঃ 7 এর জন্য অনেক গুলা রুলস আছে। যেমনঃ কোন নাম্বারে প্রাইম ফ্যক্টরাইজেশনে প্রাইম ফ্যাক্টর হিসাবে 7 থাকলে সেটা 7 দ্বারা বিভাজ্য৷
হায় হায় কি হইলো? এখন এতো বড় নাম্বারের প্রাইম ফ্যাক্টরাইজেশন করবো কিভাবে? 😭
কান্নার কিছু নাই, বলেই তো দিয়েছি অনেক গুলা রুলস আছে।
তাহকে সবচাইতে সহজ নিয়ম টা হলোঃ
যে নাম্বারটা দেওয়া থাকবে সেই সংখ্যাটার শেষ থেকে ৩টা করে নাম্বর নিয়ে একটা গ্রুপ করবো। যদি নাম্বারটা দেওয়া থাকে 6913580247
১ম গ্রুপঃ 247 ২য় গ্রুপঃ 580 ৩য় গ্রুপঃ 913 ৪র্থ গ্রুপঃ 6 ( একটা ডিজিট অবশিষ্ঠ আছে তাই, বেশী থাকলে সেটাই লিখতাম)
এখন ১ম গ্রুপকে যোগ, ২য় গ্রুপে বিয়োগ, ৩ গ্রুপ কে যোগ, ৪র্থ গ্রুপ কে বিয়োগ করবো। যতগুলো গ্রুপ থাককনা কেন একই ভাবে আগাবো।
মোট যে সংখ্যা হবে, তা যদি 7 দিয়ে বিভাজ্য হয় তাহলে মোট সংখ্যাটাও 7 দিয়ে বিভাজ্য হবে৷
যেমনঃ উদাহরণ টাই শেষ করি
+247 -580 +913 – 6 [আমরা ধারার ন্যায় চিন্তা করতে পাড়ি 247–580+980–6 = 574]
total sum : 574 যা 7 (574÷7=82) দ্বারা বিভাজ্য তাই 6913580247 সংখ্যাটি 7 দ্বারা অবশ্যই বিভাজ্য।
অনেকেই হয়তো প্রতিবার এই শেষের 3টা ডিজিট নিয়ে গ্রুপ করা তারপর যোগ বিয়গ করা নিয়ে চিন্তায় পরে গেছো। আসলে বেপারটা সিম্পল। চিন্তা করো পেয়ে যাবা। 🙂
8 এর জন্য রুলঃ কোন সংখ্যার শেষের 3 টা ডিজিট যদি 8 দ্বারা ভাগ যায় তাহলে সেই সংখ্যাটা অবশ্যই 8 দ্বারা ভাগ যায়।
যেমনঃ 6913580248 নাম্বারের শেষের ৩টা ডিজিট 248 যা 8 দ্বারা বিভাজ্য তাই পুরো সংখ্যাটি অবধ্যই 8 দ্বারা বিভাজ্য।
9 এর জন্য রুলঃ কোন সংখ্যার প্রতিটা ডিজিটের যোগফল যদি 9 দ্বারা বিভাজ্য হয় তাহলে সম্পুর্ণ সংখ্যাটি 9 দ্বারা বিভাজ্য। ( অনুরুপ 3 এর রুল এর মত)
যেমনঃ 1236393 এর প্রতিটা ডিজিটের যোগফলঃ 1+2+3+6+3+9+3=27 যা 9 দ্বারা (27÷9=3) বিভাজ্য।সুতরাং সম্পুর্ণ সংখ্যাটি 9 দ্বারা বিভ্যাজ।
10 এর জন্য রুলঃ যে সংখ্যার শেষের ডিজিট 0 কেবল মাত্র সেই সংখ্যাগুলোই 10 দ্বারা বিভাজ্য।
11 জন্য রুলঃ প্রতিটা সংখ্যাকে একটি গ্রুপ ধরে ( 7 এর মত কিছুটা) প্রথম থেকে ডিজিট গুলো পর্যায়ক্রমে যোগ, বিয়োগ করতে থাকবো। সম্পুর্ন ফলাফল যদি 11 দ্বারা বিভাজ্য হয় তাহলে সম্পুর্ণ নাম্বারটি 11 দ্বারা বিভাজ্য।
যেমনঃ 145816 সংখ্যাটির জন্য প্রতিটা সংখ্যাকে গ্রুপ ধরলে এরুপ হবেঃ
1–4+5–8+1–6= -11 যা 11 দ্বারা বিভাজ্য (-11%11=0) তাই সম্পুর্ণ সংখ্যাটি 11 দ্বারা বিভাজ্য।
12 এর জন্য রুলঃ কোন সংখ্যা যৌথ ভাবে 3 এবং 4 দিয়ে বিভাজ্য হলে সংখ্যাটি অবশ্যই 12 দ্বারা বিভাজ্য।
যেমনঃ 144 যা উপরুক্ত রুলস অনুসারে 3 এবং 4 দ্বারা বিভাজ্য তাই সংখ্যাটি অবশ্যই 12দ্বারা বিভাজ্য।
অবশেষে অনেক বকবকানির পরে 1 থেকে 12 জন্য Divisible রুল আমরা জানলাম। এখন প্রতিটা সংখ্যার জন্য যদি একটা করে ফাংশন তৈরী করি তাহলেই কাজ শেষ।
এতোক্ষনে সবার প্রবলেমটি Accepted হয়ে যাওয়ার কথা। যদি না হয়ে থাকে, নিচের Solution এ একটু চোখ বুলিয়ে আসো। তারপর কোডটা নিজে করো।

Solution Code Two:

হ্যাপি কোডিং