Find number of subset such that their GCD = g
সমস্যাঃ
n(<=1e5) সাইজের একটি অ্যারে a দেয়া থাকবে যেখানে a[i] <= 1e5 এবং Q(<=1e5) টি কুয়েরী থাকবে। প্রতি কুয়েরী তে একটি সংখ্যা g দেয়া থাকবে। বলতে হবে অ্যারে তে এমন কয়টি সাবসেট আছে যাদের GCD = g.
বিঃদ্রঃ এই প্রব্লেমটি পূর্বে আলোচিত এই প্রব্লেম এর অনুরূপ একটি প্রব্লেম।
আইডিয়াঃ
১) প্রথমত, আমরা চেষ্টা করবো এমন কয়টি সাবসেট বানানো সম্ভব যাদের GCD g অথবা এর মাল্টিপল। এই কাজটি আমরা কিভাবে করতে পারি?
1 থেকে 10^5 পর্যন্ত সবার ফ্রিকুয়েন্সী কাউন্ট করে রাখবো। এরপর, প্রতিটি সংখ্যার জন্য তার সম্ভাব্য সকল মাল্টিপল এর ফ্রিকুয়েন্সি যোগ করে পাবো এমন কয়টি সংখ্যা আছে যা ঐ সংখ্যা দ্বারা ভাগ করা যায়।
এখন, x দ্বারা বিভাজ্য এমন মোট অ্যারে এলিমেন্ট y হলে, yC1 + yC2 + yC3 + ---- + yCy = (2^y)-1 টি সাবসেট সম্ভব যাদের GCD g অথবা এর মাল্টিপল।
২) এখন, প্রতিটি সংখ্যা x এর জন্য এক্সেক্ট কতোগুলো সাবসেট আছে যাদের GCD = g? আমি যদি বের করতে পারি x এর প্রতিটি মাল্টিপল এর জন্য এক্সেক্ট সাবসেট কতোটি আছে তাহলে x এর জন্যও বের করতে পারি। বুঝতেই পারতেছো এই কাজটি বড় থেকে ছোট অর্ডারে করতে হবে।
Comments
Post a Comment