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

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

Magic In Grid

At Coder Educational DP-B | DP Series(Episode-2)