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