Cod sursa(job #588182)
Utilizator | Data | 7 mai 2011 10:46:38 | |
---|---|---|---|
Problema | Indep | Scor | 20 |
Compilator | cpp | Status | done |
Runda | juniori_2011_1 | Marime | 0.5 kb |
#include<stdio.h>
int n,x[501],a[501][1001];
int cmmdc(int a,int b) {
int r;
while (b!=0) {
r=a%b;
a=b;
b=r;
}
return a;
}
int main() {
int i,j,d;
freopen("indep.in","r",stdin);
freopen("indep.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i) {
scanf("%d",&x[i]);
}
a[1][0]=a[1][x[1]]=1;
for(i=2;i<=n;++i) {
for(j=0;j<=1000;++j) if(i!=1 || j!=1) {
d=cmmdc(x[i],j);
a[i][d]+=a[i-1][j];
a[i][j]+=a[i-1][j];
}
}
printf("%d",a[n][1]);
return 0;
}