101 Hack 45 : C. The Chosen One

惜しくもTシャツ圏内ならず。
https://www.hackerrank.com/contests/101hack45/challenges/the-chosen-one

問題

N個の整数A[i]が与えられる。
これらに対し、(N-1)個の整数の約数ではあるが、残り1つの約数ではないようなものが存在すればそれを応えよ。

解法

数列の左右方向からf(L) = GCD(A[0],A[1],A[2]...A[L])と g(R) = GCD(A[N-1],A[N-2],A[N-3]...A[R])を順次求めて行こう。
A[x]がGCD(f(x-1),g(x+1))の倍数でないなら、GCD(f(x-1),g(x+1))が解。

int N;
ll A[101010];
ll L[101010];
ll R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	L[0]=A[0];
	for(i=1;i<=N-1;i++) L[i]=__gcd(L[i-1],A[i]);
	R[N-1]=A[N-1];
	for(i=N-2;i>=0;i--) R[i]=__gcd(R[i+1],A[i]);
	
	if(N==1) {
		cout<<A[0]+1<<endl;
		return;
	}
	
	FOR(i,N) {
		if(i==0) {
			if(A[0]%R[1]) {
				cout<<R[1]<<endl;
				return;
			}
		}
		else if(i==N-1) {
			if(A[i]%L[i-1]) {
				cout<<L[i-1]<<endl;
				return;
			}
		}
		else {
			ll v = __gcd(L[i-1],R[i+1]);
			if(A[i]%v) {
				cout<<v<<endl;
				return;
			}
		}
	}
	
}

まとめ

ここら辺はまだ簡単。