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 এর জন্যও বের করতে পারি। বুঝতেই পারতেছো এই কাজটি বড় থেকে ছোট অর্ডারে করতে হবে। 

	#define ll long long int
	#define sz 100005
	ll ara[sz],fre[sz],divbyi[sz],gcdgreater[sz],exact[sz];
	void Solve(int t)
	{
	ll i,j,k,n,q,g;
	cin>>n>>q;
	for(i=1 ; i<=n ; i++){
	cin>>ara[i];
	fre[ara[i]]++;
	}
	/** Count number of elements those r divisible by i **/
	for(i=1 ; i<=1e5 ; i++){
	for(j=i ; j<=1e5 ; j+=i)
	divbyi[i] += fre[j];
	}
	/** Count number of subsets such that their GCD is i or multiple of i **/
	for(i=1 ; i<=1e5 ; i++){
	gcdgreater[i] = (1LL << divbyi[i])-1;
	}
	/** Count exact number of subset such that their GCD = g **/
	for(i=1e5 ; i>=1 ; i--){
	exact[i] = gcdgreater[i];
	for(j=i+i ; j<=1e5 ; j+=i)
	exact[i] -= exact[j];
	}
	for(i=1 ; i<=q ; i++){
	cin>>g;
	cout<<exact[g]<<endl;
	}
	}

view raw SubSet GCD.cpp hosted with ❤ by GitHub