C++求去掉数组中的一些元素使得最大公因数发生变化

Question

#include<bits/stdc++.h>
using namespace std;
long long n;
long long a[10000000];
bool check(long long x)//x块会变化 
{
    long long i,g=a[1],t;
    for(i=1;i<=n;i++)//所有元素的公因数 
    {
        g=__gcd(g,a[i]);
        t=g;
    }
    g=a[n];
    for(i=n;i>x;i--)
    {
        g=__gcd(g,a[i]);
        cout<<g<<" ";
    } 
    cout<<endl;
    if(t<g)
    return 1;
    else
    return 0; 
}
int main()
{
   cin>>n;
   long long i;
   for(i=1;i<=n;i++)
   cin>>a[i];
   sort(a+1,a+1+n);
   for(i=1;i<=n;i++)
   cout<<a[i]<<" ";
   cout<<endl;
   if(check(n)==0)
   {
     cout<<-1;
        return 0;
   }
   else
   {
   long long l=0,r=n,mid;
   while(l<r)
   {
       mid=(r+l)/2;
       if(check(mid))
       r=mid;
       else
       l=mid+1;
   }    

   return 0; 
}
} 

这个应该怎么改才能实现去掉数组a中的一些元素使得最大公因数发生变化啊？
比如说这组数据这里输出时19，但是应该输出9才对啊
20
524 91 152 743 939 133 768 761 671 780 728 742 509 364 376 132 956 594 963 359

Answer 1

通过删除数组中的一些元素，使得数组的最大公因数发生变化。然而，从你给出的代码中，我发现存在几个问题需要修复和调整。

首先，你使用了check函数来检查最大公因数是否发生变化，但是这个函数的逻辑是检查给定块（x）的元素与所有元素的公因数是否改变。这个逻辑是错误的。我们需要在给定块（x）的元素和剩余元素之间找到最大公因数，然后比较这个公因数和之前的最大公因数是否相等。

其次，你需要调整输入、输出和变量声明部分的代码。你需要在main函数中声明变量，而不是在全局范围内声明。此外，你应该使用std::cout和std::cin来进行输入和输出。

以下是修改后的代码：

#include<bits/stdc++.h>
using namespace std;

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

bool check(long long x) { //x块会变化 
    long long i, g = 0, t;
    for(i = 1; i <= x; i++) { //所有元素的公因数 
        g = gcd(g, a[i]);
        t = g;
    }
    g = a[x];
    for(i = x; i < n; i++) { //剩余元素的最大公因数 
        g = gcd(g, a[i]);
        cout << g << " ";
    }
    cout << endl;
    if(t < g)
        return 1; //最大公因数发生变化 
    else
        return 0; //最大公因数未发生变化 
}

int main() {
    cin >> n;
    long long i;
    long long a[10000000];
    for(i = 1; i <= n; i++) { //输入数组元素 
        cin >> a[i];
    }
    sort(a+1,a+1+n); //对数组进行排序 
    for(i = 1; i <= n; i++) { //输出排序后的数组 
        cout << a[i] << " ";
    }
    cout << endl;
    if(check(n) == 0) { //检查最大公因数是否发生变化 
        cout << -1; //未发生改变 
        return 0; 
    } else { //找到第一个使得最大公因数发生变化的元素并删除 
        long long l = 0, r = n, mid;
        while(l < r) {
            mid = (r + l) / 2; //二分查找找到第一个使得最大公因数发生变化的元素的位置 
            if(check(mid)) { //如果最大公因数发生变化，记录该位置并返回 
                cout << a[mid] << endl; //输出该元素 
                return 0; 
            } else { //如果最大公因数未发生变化，继续查找 
                l = mid + 1; 
            }
        }       
    }   
    return 0; //未找到使得最大公因数发生变化的元素 
}