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) যোগ করলেই এন্সার পেয়ে যাবো।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Comments
Post a Comment