Cod sursa(job #2595166)

Utilizator mihai50000Popescu Mihai mihai50000 Data 7 aprilie 2020 11:50:18
Problema Indep Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.5 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1001;
const int BOUND = 1000;

int v[DIM];
int cnt[DIM];
int aux[DIM];

main()
{
	int n;
	fin >> n;
	
	for(int i = 1; i <= n; ++i)
	{
		fin >> v[i];
	}
	
	cnt[0] = 1;
	
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 0; j <= BOUND; ++j)
		{
			aux[__gcd(v[i], j)] += cnt[j];
		}
		
		for(int j = 1; j <= BOUND; ++j)
		{
			cnt[j] += aux[j];
			aux[j] = 0;
		}
	}
	
	fout << cnt[1] << '\n';
}