暴力做法：枚举$a_i$，计算除它外的其他元素的最大公约数。时间复杂度为$O(n^2 \log n)$，超时。

我们可以预处理出两个数组$l$和$r$：

• $l_i$表示$a_1$~$a_i$的最大公约数
• $r_i$表示$a_i$~$a_n$的最大公约数

然后对于$a_i$，只需要再求一遍$\gcd(l_{i-1},r_{i+1})$即可。需要特判$a_1$和$a_n$。

时间复杂度为$O(n)$，可以通过。

AC code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,a[N],l[N],r[N];
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(i==1)
            l[i]=a[i];
        else
            l[i]=__gcd(a[i],l[i-1]); // c++自带的__gcd函数
    }
    for(ll i=n;i>=1;i--)
        if(i==n)
            r[i]=a[n];
        else
            r[i]=__gcd(a[i],r[i+1]);
    printf("%lld ",r[2]); // 除去a[1]外其他元素的最大公约数
    for(ll i=2;i<n;i++)
        printf("%lld ",__gcd(l[i-1],r[i+1]));
    printf("%lld",l[n-1]); // 除去a[n]外其他元素的最大公约数
    return 0;
}