AtCoder Beginner Contest 125 C問題

AtCoder 最大公約数 累積GCD

C - GCD on Blackboard

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


#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; 
}