gcd(C - GCD on Blackboard)

atcoder.jp
これは300点問題なんだけど、なんか話題になっていたので

まずユークリッドの互除法でgcdを求めるコードを書いておく。これの計算量はラメの定理により十進法での桁数くらいらしいですね（知らなかった）、すごい。

まず、書き換える時は10^9以下なら何にしてもいいので、他の数の最大公約数にすればいいです。これを愚直に試すと、取り除くのを選ぶループで10^5、その中で10^5個のgcdを計算しなければいけないので10^10かかってしまいます。
ここでなんですが、その数の前までと後まででgcdをそれぞれ求めておけば、その前と後のgcdのgcdを取ればいいです。
それぞれ10^5回計算しておけば、取り除くのを選ぶループだけで求められます。（累積和の応用っぽい）
計算量は多分10^5

なんかセグ木でやる解法があるらしいけどしなくても良くない…？実は私はセグ木使ったことないよ（それも良くないので後でそのバージョンも考えて実装します）

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

long long int gcd(ll int a,ll int b){
    if(a==0||b==0)return max(a,b);
    ll int mi=min(a,b);ll int ma=max(a,b);
    ll int c=ma%mi;
    return gcd(mi,c);
}
int N;
ll int A[100004];
ll int bef[100004];
ll int aft[100004];
int main(void){
    scanf("%d",&N);
    rep(i,N)scanf("%lld",&A[i]);
    rep(i,N){
        if(i==0)continue;
        i==1 ? bef[i]=A[i-1] : bef[i]=gcd(bef[i-1],A[i-1]);
    }
    rep(i,N){
        int j=N-1-i;if(j==N-1)continue;
        j==N-2 ? aft[j]=A[j+1] : aft[j]=gcd(aft[j+1],A[j+1]);
    }
    ll int ans=0;
    rep(i,N){
        if(i==0)ans=max(ans,aft[i]);
        else if(i==N-1)ans=max(ans,bef[i]);
        else ans=max(ans,gcd(bef[i],aft[i]));
    }
    printf("%lld\n",ans);
}

すぐ思いついたけど、まあ300点にしては難しそう（簡単めな500くらいかな）
Cが解けなくて落ち込んでた人がいたけど気にしなくて良いと思います