Cod sursa(job #2608918)

Utilizator As932Stanciu Andreea As932 Data 1 mai 2020 21:08:18
Problema Indep Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int vMax=1005;

int n,nr;

struct bigN
{
    int v[vMax*3];
}dp[vMax];

void ad(int v1[],int v2[])
{
    int c=0,nr;

    for(int i=1;i<=max(v1[0],v2[0]);i++)
    {
        nr=c+v1[i]+v2[i];//adunam vectorii
        c=nr/10;
        v1[i]=nr%10;
    }

    v1[0]=max(v1[0],v2[0]);

    while(c)
    {
        v1[++v1[0]]=c%10;
        c/=10;
    }
}

int main()
{
    fin>>n;

    dp[0].v[0]=1;
    dp[0].v[1]=1;

    for(int i=1;i<=n;i++)
    {
        fin>>nr;

        for(int j=1;j<=1000;j++)
            if(dp[j].v[0])
            {
                int gcd=__gcd(nr,j);

                ad(dp[gcd].v,dp[j].v);
            }

        ad(dp[nr].v,dp[0].v);
    }

    if(dp[1].v[0])
    {
        for(int i=dp[1].v[0];i>0;i--)
            fout<<dp[1].v[i];
    }
    else
        fout<<"0";

    return 0;
}