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)

	#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,g,gcdsum=0;
	cin>>n;
	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;
	}
	/** 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];
	gcdsum += (exact[i] * i);
	}
	cout<<gcdsum<<endl;
	}

view raw All pair gcd sum.cpp hosted with ❤ by GitHub