C - GCD on Blackboard

コンテスト中は手も足も出なかったが、以下の非常にわかりやすい説明を受けて何とか実装できた。

Cの解法です pic.twitter.com/isCis7Kjk7

— アルメリア (@armeria_betrue) April 27, 2019

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a<b) gcd(b,a);
while(a%b){
int r=a%b;
a=b;b=r;
}
return b;
}
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int i=0; i<N; i++){
cin >> A.at(i);
}
vector<int> pre(N); 
       //累積GCD（前から）
      
vector<int> suf(N); 
       //累積GCD（後から）
      
pre.at(0) = A.at(0);
suf.at(N-1) = A.at(N-1);
for (int i=1; i<N; i++){
pre.at(i) = gcd(pre.at(i-1), A.at(i));
}
for (int i = N-2; i>=0; i--){
suf.at(i) = gcd(suf.at(i+1), A.at(i));
}
int ans = suf.at(1); 
       // 2番目以降の累積GCD
      
for (int i=1; i<N-1; i++){
ans = max(ans, gcd(pre.at(i-1), suf.at(i+1)));
}
ans = max(ans, pre.at(N-2)); 
       // 一番後ろ以外の累積GCD
      
cout << ans << endl;
}