AtCoder - Grand Contest 038 - LCMs

Problem Description here

প্রব্লেমঃ প্রব্লেমটিতে মূলত বলা হয়েছে, n সাইজের একটি অ্যারে a দেয়া থাকবে যেখানে n<=2e5 এবং a[i]<=1e6.
অ্যারের All Possible Pair এর LCM এর যোগফল বের করতে বলা হয়েছে। 

এই প্রব্লেমটি সলভ করার জন্য Prerequisite-1 এবং Prerequisite-2 দুইটি পর্ব অবশ্যই পড়তে হবে। 

সল্যুশন আইডিয়াঃ

১) আমরা জানি, LCM(ai , aj) = (ai * aj) / GCD(ai , aj)। এখন, g GCD সম্বলিত কয়েকটি পেয়ার যদি (x1 , y1) , (x2 , y2) , (x3 , y3) হয় তবে পেয়ারগুলোর LCM এর যোগফল কী হবে?

LCMSUM = ( (x1*y1) + (x2*y2) + (x3*y3) ) / g

২) এখন, একটি অ্যারে pairsum নিবো। pairsum[i] এর মধ্যে প্রাথমিকভাবে এমন সব পেয়ার এর গুণফলের যোগফল থাকবে যাদের GCD i অথবা i এর মাল্টিপল। 

৩) এখন, একটি অ্যারে a[] = {1 , 2 , 3 , 4 , 6 , 12} হলে, GCD 2 অথবা এর মাল্টিপল হবে কাদের?
{2 , 4 , 6 , 12} এই সেট এর পেয়ারগুলোর।

All possible pairsum = (2*4) + (2*6) + (2*12) + (4*6) + (4*12) + (6*12)

এটিকে কীভাবে লিখা যায়?

( ( (2+4+6+12) * (2+4+6+12)) - (2^2 + 4^2 + 6^2 + 12^2) )/2

মানে সেট টি {x1 , x2 , ... , xn} হলে, 

All possible pairsum = (  (summation(xi))^2 - summation(xi^2)  )/2

৪) এখন, পূর্বের প্রব্লেমগুলোতে এক্সেক্ট কয়টা পেয়ার আছে যাদের GCD = i এই কাজ করার সময় GCD = i এমন পেয়ারগুলোর গুণফলের যোগফল বের করে ফেলতে পারবো। কারণ, আমার কাছে প্রাথমিকভাবে ক্যালকুলেট করা আছে i অথবা এর মাল্টিপল এমন পেয়ারগুলোর গুণফলের যোগফল। 

৫) সবশেষে, প্রতিটি x এর জন্য sum এর সাথে (pairsum[x] / x) যোগ করলেই এন্সার পেয়ে যাবো। 



#include<bits/stdc++.h>
#define ll long long int
#define scln(x) sc("%lld",&(x))
#define MOD 998244353
#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
using namespace std;
ll BigMod(ll a,ll b)
{
if(b == 0)return 1%MOD;
else if(b%2 == 0)
{
ll temp=BigMod(a,b/2);
return ((temp%MOD)*(temp%MOD))%MOD;
}
else
{
return ((a%MOD)*BigMod(a,b-1)%MOD)%MOD;
}
}
#define sz 1000005
ll ara[sz],fre[sz],divbyi[sz],gcdgreater[sz],exact[sz],pairsum[sz];
void Solve(int t)
{
ll i,j,k,n,ans=0;
scln(n);
for(i=1 ; i<=n ; i++)
{
scln(ara[i]);
fre[ara[i]]++;
}
/** Count number of elements those r divisible by i & calculate sum of multiple of pair whose GCD is i or multiple of i **/
for(i=1 ; i<=1e6 ; i++)
{
ll sum = 0, sqsum = 0;
for(j=i ; j<=1e6 ; j+=i)
{
divbyi[i] += fre[j];
sum = (sum + (fre[j] * j)%MOD)%MOD;
sqsum = (sqsum + (fre[j] * ((j*j)%MOD))%MOD)%MOD;
}
sum = (sum * sum)%MOD;
ll temp = (sum - sqsum + MOD)%MOD;
pairsum[i] = (temp * BigMod(2 , MOD-2))%MOD;
}
/** Count number of pairs those GCD is i or multiple of i **/
for(i=1 ; i<=1e6 ; i++){
if(divbyi[i] >= 1)
gcdgreater[i] = (divbyi[i] * (divbyi[i]-1))/2;
}
/** Count exact number of pairs those GCD is equal to i & sum of multiple of pair whose GCD is exactly i **/
for(i=1e6 ; i>=1 ; i--){
exact[i] = gcdgreater[i];
for(j=i+i ; j<=1e6 ; j+=i){
exact[i] -= exact[j];
pairsum[i] = (pairsum[i] - pairsum[j] + MOD)%MOD;
}
if(exact[i] == 0)
continue;
ll temp = (pairsum[i] * BigMod(i , MOD-2))%MOD;
ans = (ans + temp + MOD)%MOD;
}
cout<<ans<<endl;
}
int main()
{
int t,T;
T = 1;
RUN_CASE(t,T)
{
Solve(t);
}
return 0;
}
view raw temp3.cpp hosted with ❤ by GitHub

Comments

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

At Coder Educational DP-B | DP Series(Episode-2)