主要思路

蛮好想。考虑暴力，求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速？我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一，所以我们直接预处理\(a_i\)的因数，然后回答询问时直接\(\log n\)枚举即可。

代码

// UOJ#3A.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAX_N = 1e6 + 200;

ll n, ai[MAX_N], primes[MAX_N];

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    for (int i = 1; 1LL * i * i <= ai[1]; i++)
        if (ai[1] % i == 0)
        {
            primes[++primes[0]] = i;
            if (ai[1] / i != i)
                primes[++primes[0]] = ai[1] / i;
        }
    sort(primes + 1, primes + 1 + primes[0]);
    for (int i = 1; i <= n; i++)
    {
        bool flag = true;
        ll di = gcd(ai[1], ai[i]);
        for (int j = 1; j <= primes[0]; j++)
            if (di % primes[j] == 0 && di / primes[j] < di)
            {
                printf("%lld ", di / primes[j]);
                flag = false;
                break;
            }
        if (flag)
            printf("-1 ");
    }
    return 0;
}