Disclude a number in a sequence so that the greatest divisor common of all the others at most. Find that GCD and the position of that discluded one.

Question

Problem. Disclude a number in a sequence so that the greatest divisor common of all the others at most. By programming, find that GCD and the position of that discluded one.

My code in the environment C++ is:

#include <iostream>
using namespace std;
int gcd(int x, int y) {
    while (y) {
        int r=x%y;
        x=y;
        y=r;
    }
    return x;
}
int pcd(int arr[], int u, int w) {
    int temp=arr[u];
    arr[u]=0;
    int result=0;
    for (int i=1; i<=w; i++) {
        result=gcd(result, arr[i]);
    }
    arr[u]=temp;
    return result;
}
int main() {
    int n;
    cin>>n;
    int a[100000];
    for (int i=1; i<=n; i++) {
        cin>>a[i];
    }
    int t=0;
    int v;
    for (int j=1; j<=n; j++) {
        if (pcd(a, j, n)>t) {
            t=pcd(a, j, n);
            v=j;
        }
    }
    cout<<v<<" "<<pcd(a, v, n);
}

This is buffalo-way, I substituted the discluded one by $0,$ then replace $0$ by that discluded number and compare all the GCDs we have, that consumed time. How can we speed up the process ? I need to the help, thanks a real lot !

Answer 1

Think of the FFT.
The numbers are $a_k$
$b_k=gcd(a_{2k-1},a_{2k})$.
Solve the problem for the $n/2$ numbers $b_k$, get $c_k$.
Do gcd $(c_k,a_{2k_-1})$ and gcd $(c_k,a_{2k})$.