candidatas_merge_gcd_pref.cpp

struct Node
{
	vector<pair<int,int>> pref, suf;
	int gcd_td; // MDC do intervalo completo
};

int gcd(int a, int b) {return !b?a:gcd(b, a%b);}

Node combine(Node l, Node r) {
	Node ret;
	ret.gcd_td = gcd(l.gcd_td, r.gcd_td);
	
	ret.pref = l.pref;
	if(l.gcd_td > 1) {
		for(pair<int,int> x : r.pref) {
			int val = gcd(x.first, ret.pref.back().first);
			if(val == 1) break; // não queremos salvar os intervalos com MDC 1 para simplificar a resposta
			if(val != ret.pref.back().first)
				ret.pref.pb({val, x.second});
			else ret.pref.back().second += x.second;
		}
	}
	// lembre-se de fazer a mesma coisa para o sufixo
	// não está mostrado aqui para simplificar o código
	return ret;
}