Cod sursa(job #2610389)

Utilizator Rares31100Popa Rares Rares31100 Data 4 mai 2020 20:18:44
Problema Indep Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("indep.in");
ofstream out("indep.out");

int n,a[501],toAdd[501];
string nr="10",sum="0";

int cmmdc(int a,int b)
{
    int rest;
    while(b)
    {
        rest = a%b;
        a=b;
        b=rest;
    }

    return a;
}


string add(string a,string b)
{
    string c;
    c.resize( max(a.size(),b.size())+4 );

    for(int i=0;i<c.size()-1;i++)
    {
        c[i] += (i<a.size()?a[i]-'0':0) + (i<b.size()?b[i]-'0':0);
        c[i+1] = c[i]/10;
        c[i] = c[i]%10 + '0';
    }
    c.erase(c.end()-1);
    while(c.size()>1 && c[c.size()-1]=='0')
        c.erase(c.end()-1);

    return c;
}


string mult(string a,int nr)
{
    string c;
    c.resize( a.size()+4 );

    for(int i=0,val,p;i<a.size()+4;i++)
    {
        val = (i<a.size() ? a[i]-'0' : 0)*nr + c[i];
        p = i; c[i] = 0;

        while(val)
        {
            c[p] += val%10;
            val/=10;
            p++;
        }

        c[i] += '0';
    }

    while(c.size()>1 && c[c.size()-1]=='0')
        c.erase(c.end()-1);

    return c;
}

int main()
{
    in>>n;

    for(int i=1;i<=n;i++)
        in>>a[i];

    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if( cmmdc(a[i],a[j])==1 )
                toAdd[n-j]++;

    for(int i=0;i<=n;i++)
    {
        sum = add(sum, mult(nr,toAdd[i]));
        nr = mult(nr,2);
    }

    for(int i=sum.size()-1;i>=0;i--)
        out<<sum[i];

    return 0;
}