Cod sursa(job #2595197)

Utilizator mihai50000Popescu Mihai mihai50000 Data 7 aprilie 2020 12:16:01
Problema Indep Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1000;
 
int cnt[DIM + 1][DIM + 1];

void add(int x, int y)
{
	int r = 0;
	
	cnt[x][0] = max(cnt[x][0], cnt[y][0]);
	
	for(int i = 1; i <= cnt[y][0] || i <= cnt[x][0]; ++i)
	{
		r += cnt[x][i];
		r += cnt[y][i];
		
		cnt[x][i] = r % 10;
		r /= 10;
	}
	
	while(r)
	{
		cnt[x][++cnt[x][0]] = r % 10;
		r /= 10;
	}
}

main()
{
	int n;
	fin >> n;
	
	cnt[0][0] = cnt[0][1] = 1;
	
	for(int i = 1; i <= n; ++i)
	{
		int x;
		fin >> x;
		
		for(int j = 1; j <= DIM; ++j)
			if(cnt[j][0] != 0)
				add(__gcd(x, j), j);
		
		add(x, 0);
	}
	
	if(cnt[1][0] == 0)
		fout << 0 << '\n';
	else
	{
		for(int i = cnt[1][0]; i >= 1; --i)
			fout << cnt[1][i];
	}
}