Seletiva IOI 2014

risco.cpp

// Ivan Carvalho
// Risco - Seletiva IOI - OBI 2014
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	if(a < b) swap(a,b);
	if(b == 0) return a;
	return gcd(b,a%b);
}
int main(){
	long long resp = 0;
	int n,L,R;
	scanf("%d %d %d",&n,&L,&R);
	map<int,int> velho,novo;
	map<int,long long> grande;
	for(int i=1;i<=n;i++){
		novo.clear();
		velho[0]++;
		int x;
		scanf("%d",&x);
		for(map<int,int>::iterator it = velho.begin();it != velho.end();it++){
			int y = (*it).first;
			int qtd = (*it).second;
			int mdc = gcd(x,y);
			if(mdc <= L){
				resp += 1LL*(R - L + 1)*qtd;
			}
			else if(L <= mdc && mdc <= R){
				resp += 1LL*(R - mdc + 1)*qtd;
			}
			novo[mdc] += qtd;
		}
		velho = novo;
	}
	printf("%lld\n",resp);
	return 0;
}