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 এই কাজটি সহজেই করা যাবে। 

	#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 pairs those GCD is greater than or equal to i **/
	for(i=1 ; i<=1e5 ; i++){
	if(divbyi[i] >= 1){
	gcdgreater[i] = (divbyi[i] * (divbyi[i] - 1))/2; /** Number of ways to choose 2 elements from n = (n*(n-1))/2 **/
	}
	}
	/** Count exact number of pairs those GCD is equal to i **/
	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 GCD pair.cpp hosted with ❤ by GitHub