题解：

tags:[预处理][gcd]

故事背景：光头钻进了茫茫人海。

这是一个典型の通过前缀后缀和来降低复杂度的问题。

先用pre数组与suf数组分别维护前缀gcd和后缀gcd。

如果 a[i] % gcd(pre[i-1], suf[i+1]) != 0;

那么光头就从人群中钻出来了！

gcd(pre[i-1],suf[i+1])就是我们要的答案。

注意n=1时的特判！

code：

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long LL;const int NICO = 100000 + 10;int n; vector
        
          v;LL a[NICO], pre[NICO], suf[NICO];LL gcd(LL x, LL y){    return (y==0)?x:gcd(y, x%y);}int main(){    scanf("%d", &n);    for(int i=1;i<=n;i++)    {        cin >> a[i];    }    if(n == 1)    {        cout << (LL)2e18 << endl;    } else {        int pos = 0;        pre[1] = a[1]; suf[n] = a[n];        for(int i=2;i<=n;i++)        {            pre[i] = gcd(a[i], pre[i-1]);        }        for(int i=n-1;i>=1;i--)        {            suf[i] = gcd(a[i], suf[i+1]);        }        for(int i=2;i<=n-1;i++)        {            LL tmp = gcd(pre[i-1],suf[i+1]);            if(a[i] % tmp)            {                pos = i;            }        }        if(a[1] % suf[2])   pos = 1;        if(a[n] % pre[n-1]) pos = n;        // pos 表示光头出现的位置        if(pos==1) swap(a[1], a[2]), pos = 2;        LL res = a[1];        for(int i=2;i<=n;i++)        {               if(i!=pos) res = gcd(res, a[i]); // 碰见光头就跳过！        }        cout << res << endl;    }}