AtCoder - Grand Contest 038 - LCMs
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 ,...