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 , ... , xn} হলে, 

All possible pairsum = (  (summation(xi))^2 - summation(xi^2)  )/2

৪) এখন, পূর্বের প্রব্লেমগুলোতে এক্সেক্ট কয়টা পেয়ার আছে যাদের GCD = i এই কাজ করার সময় GCD = i এমন পেয়ারগুলোর গুণফলের যোগফল বের করে ফেলতে পারবো। কারণ, আমার কাছে প্রাথমিকভাবে ক্যালকুলেট করা আছে i অথবা এর মাল্টিপল এমন পেয়ারগুলোর গুণফলের যোগফল। 

৫) সবশেষে, প্রতিটি x এর জন্য sum এর সাথে (pairsum[x] / x) যোগ করলেই এন্সার পেয়ে যাবো।