Lightoj 1289 solution in Bangla

Lightoj 1289 - LCM from 1 to n solution in Bangla

Problem Link: Lightoj 1289

প্রবলেমটিতে আমাদেরকে একটি সংখ্যা  n দেয়া থাকবে । আমাদেরকে ১ হতে সেই সংখ্যা অবধি ল.সা.গু (LCM) বের করতে হবে। প্রবলেমটি সমাধান করার শুরুতেই আমরা Constrains এর দিকে যদি দেখি , সেখানে  n হতে পারে 10^8 । আর টেস্টকেসের সংখ্যা হতে পারে 10^4 । তো আমরা যদি সাধারণ ভাবে লুপ চালিয়ে LCM বের করতে যাই তাহলে আমরা TLE খেয়ে যাবো সেটা নিশ্চিত । তো এখন আমরা কি করতে পারি ?? 🤔 

আচ্ছা এবার আমরা ২টো সংখ্যার মধ্যে LCM এবং GCD বের করা শিখি (আসলে আমরা সবাই সেটা জানি । 😜 

তো মনে করি দুটো সংখ্যা a এবং b । আমরা জানি যে , যেকোনো সংখ্যাকে prime সংখ্যার গুনাকারে প্রকাশ করা যায় । 

তাহলে আমরা a এবং b  কে লিখতে পারি ,

a = p1^x1 * p2^x2 * ......

b = p1^y1 * p2^y2 * ......

এখন gcd_of_x_y = p1^min(x1,y1) * p2^min(x2,y2) * ......

এবং lcm_of_x_y = p1^max(x1,y1) * p2^max(x2,y2) * ......

উদাহরণ হিসেবে ১৬ এবং ২০ এর gcd এবং lcm বের করি, 

Prime factorization of 20 = 2^2 * 5

Prime factorization of 14 = 2 * 7

gcd_of (20,14) = 2^min(1,2) * 5^min(1,0) * 7^min(0,1)

                        =2^1 * 5^0 * 7^0

    

                        =2

lcm_of(20,14)= 2^max(1,2) * 5^max(1,0) * 7^max(0,1)

                        =2^2 * 5^1 * 7^1

                        =4*5*7

                        =140

তো আমরা দুটো সংখ্যার কিভাবে lcm এবং gcd বের করতে হয় শিখে গেলাম। এখন অনেক গুলো সংখ্যার জন্যও সেইম টেকনিক ।

a = p1^x1 * p2^x2 * ......

b = p1^y1 * p2^y2 * ......

c = p1^z1 * p2^z2 * ......

b = p1^m1 * p2^m2 * ......

gcd_of(a,b,c,d) = p1^min(x1,y1,z1,m1) * p2^min(x2,y2,z2,m2) * ......

lcm_of(a,b,c,d) = p1^max(x1,y1,z1,m1) * p2^max(x2,y2,z2,m2) * ......

তো আমাদের প্রবলেমটিতে আমাদের lcm বের করতে হবে । সেইজন্য আমাদের ১ থেকে n অবধি সব সংখ্যার প্রাইম গুলোর ম্যাক্সিমাম পাওয়ার জানতে পারলেই আমরা এটা বের করতে পারবো ।সেইজন্য তো আবার সব সংখ্যাগুলোকে prime factorize করে দেখতে হবে । সেটাও তো অনেক সময়ের ব্যাপার মানে TLE । এখন কি করা যায় 🤔।

আচ্ছা আমরা n =10  এর জন্য একটু চেষ্টা করে দেখি তো , 

1 = 2^0 * 3^0 *...😜 

2 = 2^1

3 = 3^1

4 = 2^2

5 = 5^1

6 = 2*3

7 = 7^1

8 = 2^3

9 = 3^2

10 = 2*5

LCM_of(1,2,....,10)  = 2^3 * 3^2 * 5 * 7

                                = 2520

১০ এর থেকে ছোট বা সমান প্রাইম আছে  ৪ টি (২,৩,৫,৭)

এবার যদি lcm  এর দিকে থাকাই , lcm এ ২,৩,৫,৭ মিনিমাম ১ বার করে আছেই ।

তাহলে আমরা বলতে পারি lcm এ তার থেকে ছোট বা সমান প্রাইম সংখ্যা গুলো একবার অন্তত থাকবেই । সেইজন্য আমরা এটাকে  precalculate করে রাখতে পারি ।

কিন্তু  lcm_of (1,2,..10) তে তো 2^3 এবং 3^2 আছে । আমরা সেটা কিভাবে পাবো 🤔।

আচ্ছা আমরা ১০ কে ২ দিয়ে কয়বার ভাগ করতে পারি ??

১০/২=৫

৫/২=২

২/২=১

মানে ১০ কে আমরা ৩ বার ভাগ করতে পারি ২ দিয়ে । 

এবার ১০ কে ৩ দিয়ে ভাগ কয়বার ভাগ করতে পারি ।

১০/৩=৩

৩/৩=১

তাহলে ১০ কে ৩ দিয়ে ২ বার ভাগ করা যাচ্ছে । 

আমরা কি এর পরের প্রাইম গুলো দিয়ে চেক করবো??

নাহ , করবো নাহ। কারণ আমরা ১০ থেকে ছোট বা সমান প্রাইমগুলো আগেই precalculate করে রাখবো আর সেখান থেকে ব্যবহার করবো ।

তো কত অবধি প্রাইম গুলো দিয়ে চেক করবো সেটা কতবার ভাগ যাচ্ছে??

সেটা হবে sqrt(n) । কারণ এর চেয়ে বড় কোন প্রাইমের পাওয়ার ২ হলেই সেটা n থেকে বড় হয়ে যাবে ।  

এবার দেখি Precalculate  করছি টা কি

প্রথমেই আমরা 10^8  অবধি সব প্রাইম বের করে নিবো ।

তারপর একটা অ্যারেতে প্রাইম গুলোকে গুনকারে রাখবো , তাহলে প্রতিটি প্রাইম একবার করে গুনাকারে পেয়ে যাবো।

    store[i]=store[i-1]*prime[i]; 

  

যেহেতু আমরা একবার করে প্রাইম রেখে দিচ্ছি , তাই পরে যখন আবার sqrt(n)  এর আগের প্রাইম গুলো দিয়ে চেক করবো , তখন একবার ভাগ করে নিবো । 

প্রবলেমে আমাদেরকে  2^32  দিয়ে mod  করতে বলেছে । সেটা আমরা  unsigned int  নিলে অটোমেটিক হয়ে যাবে । 

আশা করি প্রবলেমটি এবার সমাধান করতে পারবো । 

বুঝতে পারলেও কমেন্ট করতে পারেন , বুঝতে না পারলেও কমেন্ট করতে পারেন কি বুঝেন নি সেটা । 

'