Bappy's Blog

Problem Description  here প্রব্লেমঃ প্রব্লেমটিতে মূলত বলা হয়েছে, n সাইজের একটি অ্যারে a দেয়া থাকবে যেখানে n<=2e5 এবং a[i]<=1e6. অ্যারের All Possible Pair এর LCM এর যোগফল বের করতে বলা হয়েছে।  এই প্রব্লেমটি সলভ করার জন্য  Prerequisite-1  এবং  Prerequisite-2  দুইটি পর্ব অবশ্যই পড়তে হবে।  সল্যুশন আইডিয়াঃ ১) আমরা জানি, LCM(ai , aj) = (ai * aj) / GCD(ai , aj) । এখন, g GCD সম্বলিত কয়েকটি পেয়ার যদি (x1 , y1) , (x2 , y2) , (x3 , y3) হয় তবে পেয়ারগুলোর LCM এর যোগফল কী হবে? LCMSUM = ( (x1*y1) + (x2*y2) + (x3*y3) ) / g ২) এখন, একটি অ্যারে pairsum নিবো। pairsum[i] এর মধ্যে প্রাথমিকভাবে এমন সব পেয়ার এর গুণফলের যোগফল থাকবে যাদের GCD i অথবা i এর মাল্টিপল।  ৩) এখন, একটি অ্যারে a[] = {1 , 2 , 3 , 4 , 6 , 12} হলে, GCD 2 অথবা এর মাল্টিপল হবে কাদের? {2 , 4 , 6 , 12} এই সেট এর পেয়ারগুলোর। All possible pairsum = (2*4) + (2*6) + (2*12) + (4*6) + (4*12) + (6*12) এটিকে কীভাবে লিখা যায়? ( ( (2+4+6+12) * (2+4+6+12)) - (2^2 + 4^2 + 6^2 + 12^2) )/2 মানে সেট টি {x1 , x2 ,...

সমস্যাঃ n(<=1e5) সাইজের একটি অ্যারে দেয়া থাকবে যেখানে a[i]<=1e5। ঐ অ্যারের যতগুলো পেয়ার সম্ভব তাদের GCD এর যোগফল বের করতে হবে।  এই প্রব্লেমটি পূর্বে আলোচিত  এই প্রব্লেম  এর উপর পুরোপুরি নির্ভরশীল।  আইডিয়াঃ আমি যদি 1 থেকে 10^5 পর্যন্ত প্রতিটি সংখ্যা x কয়টি পেয়ার এর GCD হওয়া সম্ভব সেটা রেফারেন্সের প্রব্লেম দ্বারা বের করতে পারি তাহলে প্রতিটি সংখ্যা x এর জন্য, sum += (x * number of pair those GCD equal to x)

সমস্যাঃ n(<=1e5) সাইজের একটি অ্যারে a দেয়া থাকবে যেখানে a[i] <= 1e5 এবং Q(<=1e5) টি কুয়েরী থাকবে। প্রতি কুয়েরী তে একটি সংখ্যা g দেয়া থাকবে। বলতে হবে অ্যারে তে এমন কয়টি সাবসেট আছে যাদের GCD = g.  বিঃদ্রঃ এই প্রব্লেমটি পূর্বে আলোচিত  এই প্রব্লেম  এর অনুরূপ একটি প্রব্লেম। আইডিয়াঃ ১) প্রথমত, আমরা চেষ্টা করবো এমন কয়টি সাবসেট বানানো সম্ভব যাদের GCD g অথবা এর মাল্টিপল। এই কাজটি আমরা কিভাবে করতে পারি?  1 থেকে 10^5 পর্যন্ত সবার ফ্রিকুয়েন্সী কাউন্ট করে রাখবো। এরপর, প্রতিটি সংখ্যার জন্য তার সম্ভাব্য সকল মাল্টিপল এর ফ্রিকুয়েন্সি যোগ করে পাবো এমন কয়টি সংখ্যা আছে যা ঐ সংখ্যা দ্বারা ভাগ করা যায়।  এখন, x দ্বারা বিভাজ্য এমন মোট অ্যারে এলিমেন্ট y হলে, yC1 + yC2 + yC3 + ---- + yCy = (2^y)-1  টি সাবসেট সম্ভব যাদের GCD g অথবা এর মাল্টিপল। ২) এখন, প্রতিটি সংখ্যা x এর জন্য এক্সেক্ট কতোগুলো সাবসেট আছে যাদের GCD = g? আমি যদি বের করতে পারি x এর প্রতিটি মাল্টিপল এর জন্য এক্সেক্ট সাবসেট কতোটি আছে তাহলে x এর জন্যও বের করতে পারি। বুঝতেই পারতেছো এই কাজটি বড় থেকে ছোট অর্ডারে করতে...

Problem:   n(<=1e5)  সাইজের একটি অ্যারে a দেয়া থাকবে যেখানে a[i]<=1e5 এবং q(<=1e5) টি কুয়েরী থাকবে। প্রতি কুয়েরী তে একটি সংখ্যা g দেয়া হবে। বলতে হবে অ্যারে তে এমন কয়টি পেয়ার (i,j) আছে যাদের GCD(a[i] , a[j]) = g এবং i<j আইডিয়াঃ ১) প্রথমত, আমরা চেষ্টা করবো এমন কয়টা পেয়ার সম্ভব যাদের GCD g অথবা এর মাল্টিপল। এই কাজটি আমরা কিভাবে করতে পারি?  ১ থেকে ১০^৫ পর্যন্ত সবার ফ্রিকুয়েন্সি কাউন্ট করে রাখবো। এরপর, প্রতিটি সংখ্যার জন্য তার সম্ভাব্য সকল মাল্টিপল এর ফ্রিকুয়েন্সি যোগ করে পাবো এমন কয়টি সংখ্যা আছে যা ঐ সংখ্যা দ্বারা ভাগ যায়।  এখন, x দ্বারা বিভাজ্য এমন মোট অ্যারে এলিমেন্ট y হলে, y C 2 বা (y*(y-1))/2 টি পেয়ার আছে যাদের GCD x অথবা তার মাল্টিপল।  ২) এখন, প্রতিটি সংখ্যা x এর জন্য এক্সেক্ট কতোগুলো পেয়ার আছে যাদের GCD = x এই কাজটি সহজেই করা যাবে। 

Problem:   (A * B)%M এর ভ্যালু কত সেটা বের করতে হবে যেখানে A<=1e18 , B<=1e18 , M<=1e18 Solution:  খুব ভালোভাবে বোঝা যাচ্ছে যে, ওভারফ্লো ই এই সমস্যার মূল সমস্যা -_- এখন, একটু ভিন্নভাবে চিন্তা করি প্রব্লেমটাকে।  x + x + x + x + x = 5x ৫ টা x যোগ করে পাওয়া যোগফল আর x এর সাথে ৫ গুণ করে পাওয়া গুণফল সমান। এটিই এই সমস্যা সমাধানের মূল কনসেপ্ট!  তার মানে, A*B হচ্ছে,  B সংখ্যাক A এর যোগফল। এখনো মাথায় না ঢুকলে কোড দেখতে পারোঃ

Problem Description  here প্রব্লেমটিতে একটা সংখ্যা দেয়া থাকবে যার প্রাইম ফ্যাক্টরগুলো বের করতে বলা হয়েছে। সল্যুশন আইডিয়াঃ আমরা সাধারণত প্রাইম ফ্যাক্টরাইজ করি কীভাবে? প্রাইম জেনারেট করে স্কয়ার রুট পর্যন্ত প্রাইমগুলো দিয়ে কেটে কেটে! সেটার  (মানে আমি -_-) মূলত এই সোজা শাপটা প্রব্লেম দিয়েছে ই যাতে তোমার এই সল্যুশন TLE খায়! তাহলে উপায় কী! সবগুলো সংখ্যার ক্ষুদ্রতম প্রাইম ফ্যাক্টর বের করে নাও। যেমনঃ ৮ এর ক্ষুদ্রতম প্রাইম ফ্যাক্টর ২ , ১৫ এর ক্ষুদ্রতম প্রাইম ফ্যাক্টর ৩। মনে করো, আমি N = ৬০ এর প্রাইম ফ্যাক্টর বের করতে চাই। ৬০ পর্যন্ত সবার ক্ষুদ্রতম প্রাইম ফ্যাক্টর আমার অলরেডি জানা! Factor[] = { } step-1: SF[N] = 2 ; Add 2 to the list ; N = N/2 = 30 step-2: SF[N] = 2 ; Add 2 to the list ; N = N/2 = 15 step-3: SF[N] = 3 ; Add 3 to the list ; N = N/3 = 5 step-4: SF[N] = 5 ; Add 5 to the list ; N = N/5 = 1 Jump out from the loop!!! Now, Factor[] = { 2 , 2 , 3 , 5 } এখন, একটা সংখ্যার সর্বোচ্চ কয়টা প্রাইম ফ্যাক্টর থাকতে পারে? log(N) টা! তার মানে এক্সেক্ট log(N) বার লুপ ঘুর...