Cod sursa(job #124065)

Utilizator devilkindSavin Tiberiu devilkind Data 17 ianuarie 2008 23:46:38
Problema Indep Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 512
#define TMAX 1002
#define bs 100000000
#define sz size()
#define pb push_back

int v[NMAX];
int mx,n,i,j,k;
vector<int> nou[TMAX],old[TMAX];


vector<int> add(vector<int> t1, vector<int> t2)
{
int t=0,i;
vector<int> rez;

rez.clear();

for (i=0;(i<t1.sz)||(i<t2.sz)||(t);i++)
        {
        if (i<t1.sz) t=t+t1[i];
        if (i<t2.sz) t=t+t2[i];
        rez.pb(t%bs);
        t/=bs;
        }
        
return rez;
}

int gcd(int x,int y)
{
int a,b,r;
a=x;b=y;
r=a%b;
a=b;
b=r;
while (r)
        {
        r=a%b;
        a=b;
        b=r;
        }
return a;
}

int main()
{
freopen("indep.in","r",stdin);
freopen("indep.out","w",stdout);


scanf("%d",&n);
mx=0;

for (i=1;i<=n;i++)
        {
        scanf("%d",&v[i]);
        if (mx<v[i]) mx=v[i];
        }

for (i=1;i<=mx;i++)
        vector<int>().swap(old[i]);

old[ v[1] ].pb(1);

for (i=2;i<=n;i++)
        {
        for (j=1;j<=mx;j++)
                if (j==v[i]) {
                           //   vector<int>().swap(nou[j]);
                              nou[j].clear();
                              nou[j].pb(1);
                              }
                        else //vector<int>().swap(nou[j]);
                                nou[j].clear();

        for (j=1;j<=mx;j++)
                nou[j]=add(old[j],nou[j]);
                
        for (j=1;j<=mx;j++)
                {
                k=gcd(j,v[i]);
                nou[k] = add(nou[k],old[j]);
                }
                
        for (j=1;j<=mx;j++)
                 old[j]=nou[j];
        }

printf("%d",old[1][ old[1].sz -1 ]);

for (i=old[1].sz-2;i>=0;i--)
        printf("%08d",old[1][i]);

printf("\n");
return 0;
}