排除序列中的一个数，使得最大的除数最多为所有其他数的公共数。找到排除的索引和最大 GCD

Question

Exclude a number in a sequence so that the greatest divisor common of all the other at most. Find the index of the excluded one and that maximum greatest divisor common.

这是我的代码：

#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);
}

如何加速我的代码？已经运行超时了

Answer 1

通过累积在一个方向上应用 GCD 的结果来维护一个前缀 GCD 列表和一个后缀 GCD 列表。然后遍历列表，检查 GCD(prefix[i], suffix[i]) 的最大值。

排除序列中的一个数，使得最大的除数最多为所有其他数的公共数。找到排除的索引和最大 GCD

Exclude a number in a sequence so that the greatest divisor common of all the other at most. Find the index of the excluded one and that maximum GCD

c++

dynamic-programming

time-complexity