Find number of pairs such that their GCD = g.
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 এই কাজটি সহজেই করা যাবে।
Comments
Post a Comment