D. Winter is here: Editorial

WINTER IS HERE
Problem Link
Q. Given an array of n elements. Let the i-th element’s strength be ai. For some k he calls i1, i2, …, ik a clan if i1 < i2 < i3 < … < ik and gcd(ai1, ai2, …, aik) > 1 . He calls the strength of that clan k·gcd(ai1, ai2, …, aik). The strength of an array is the sum of strengths of all possible clans. Find strength of array.
Solution:
1. Brute Force
Find every subsequence whose gcd>1 and add it the to answer.

long g(long a,long b) //gcd{
    while(b>0)
    {
        long temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}
void func(long i,vector<long>&a, long n, long gcd, long long &ans,long k)
{
    ans=(ans+(k*gcd)%mod)%mod;
    for(long j=i+1;j<n;++j)
    {
        long t=g(gcd,a[j]);
        if(t>1)
            func(j,a,n,t,ans,k+1);
    }

}
int main()
{
    ios::sync_with_stdio(0);
    long n;
    cin>>n;
    vector<long>a(n);
    for(long i=0;i<n;++i)
        cin>>a[i];
        long i=-1;
        long long ans=0;
        for(int i=0;i<n;++i)
            if(a[i]!=1)
    func(i,a,n,a[i],ans,1);
    cout<<ans;
}

 

2. Efficient Solution
Step 1: Construction of count array
An efficient approach to find common divisors is as follows:-

  for(int i=0;i<n;++i)
    {
          for(int j=2;j*j<=a[i];++j)
        {
            if(a[i]%j==0)
            {
                count[j]++;
                if(a[i]/j!=j)
                    count[a[i]/j]++;
            }
        }
        count[a[i]]++;
    }

Count[i] contains the number of array elements who have’ i’ as their divisor.
As an example: For the array {2,3,4}
count[2]=2;   // 2 and 4
count[3]=1;   //only 3
count[4]=1;   //only 4.
Step 2: Calculating sum of subsequences with gcd as ‘i’
Q. What are the number of subsequences possible out of n elements?
Eg : For 3 elements, (a1,a2,a3)
Number of subsequences possible ensuring that for arrangement (ai aj), i a2
a3
a1 a2
a1 a3
a2 a3
a1 a2 a3
Clearly this is C(3,1)+C(3,2)+C(3,3) where C(n,k) stands for combination!
= 3+3+1=7
Suppose gcd of (a1 a2 a3) is G. Sum of strengths of these 7 clans is:-
=1*G+1*G+1*G+2*G+2*G+2*G+3*G
=(3*1)*G+(3*2)*G+(1*3)*G
=((3*1)+(3*2)+(1*3))*G
=Σ k*C(n,k)
Value of Σ k*C(n,k) is n*pow(2,n-1)
Hence
((3*1)+(3*2)+(1*3))*G= 3*pow(2,3-1)=3*pow(2,2)=12
->Now all the subsequences possible out of a set of numbers maynot be valid.
Eg: Let elements with 2 as divisor be (2 4 8)
We consider {2},{4},{8},{2,4},{2,8},{24,8},{2,4,8} all as valid clans with gcd as 2. But gcd of {4} is 4, {8} is 8 and {4,8} is 4.
To eliminate these combinations, we subtract dp[i] from all dp[j] where j is a multiple of ‘i’. Here, dp[i]=Σ k*C(n,k).
In this example, dp[2]=dp[2]-dp[4]-dp[6]-dp[8]….
The reader may verify that all the invalid cases will be eliminated after doing this step.
Answer will be Σi*dp[i].

#include
#include
#include
#define mod 1000000007
long long count[1010100],dp[1010100],power[1010100];
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    long long n;
    cin>>n;
    vector<long long>a(n);
    power[0]=1;
//Power Array
    for(long long i=1;i<1010100;++i)
    {
        power[i]=(power[i-1]*2)%mod;
    }
 long long maxi=0;
//Step 1 
     for(long long i=0;i<n;++i)
    {

          cin>>a[i];
          maxi=max(maxi,a[i]);
          for(long long j=2;j*j<=a[i];++j)
        {
            if(a[i]%j==0)
            {
                count[j]++;
                if(a[i]/j!=j)
                    count[a[i]/j]++;
            }
        }
        count[a[i]]++;
    }
//Step 2
    long long ans=0;
    for(long long i=maxi;i>=2;--i)
    {
        long long minus=0;
        if(count[i]>0)
        {
            if(i<=maxi/2)
            for(long long j=2*i;j>0&&j<=maxi;j+=i)
                minus=minus+dp[j];
            dp[i]=(count[i]*power[count[i]-1])%mod;
            dp[i]-=minus;
           dp[i]=(dp[i]%mod+mod)%mod;
            ans=(ans+(i*dp[i])%mod)%mod;
        }
        else
            dp[i]=0;
        
    }
      cout<<ans;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s