Cod sursa(job #37113)

Utilizator crawlerPuni Andrei Paul crawler Data 24 martie 2007 17:02:53
Problema Indep Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <string.h>

int cmmdc(int x,int y)
 {
  if(!y)
   return x;
    else
   return cmmdc(y,x%y);
 }


void inc(int A[], int B[])
 {  
     int i, t = 0;  

     for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)  
            A[i] = (t += A[i] + B[i]) % 10;  
    
     A[0] = i - 1;  
 }  

int a[1024][1024], b[1024][1024], v[512];
int aux[1024];

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

   int n,i,j, tmp, MAX=0;

   aux[0] = 1;
   aux[1] = 1;

   scanf("%d", &n);

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

   for(i=1;i<=n;++i)
    {
     inc(b[v[i]],aux);
     for(j=1;j<=MAX;++j)
      {
       tmp = cmmdc(v[i],j);
       inc(b[tmp],a[j]);
       inc(b[j],a[j]);
      }
     memcpy(a,b,sizeof(a));
     memset(&b,0,sizeof(b));
    }


   for(i=a[1][0]; i>0; --i)
    printf("%d",a[1][i]);

   return 0;
 }