最大公约数

[编程题]最大公约数

热度指数：68 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

我们定义任意一个序列的最大公约数为最大的能整除序列中所有数的数
例如序列 $\text \{2, 2, 4\}$ 的最大公约数为 $\text 2$ ， $\text \{1, 2, 4\}$ 的最大公约数为 $\text 1$

现在牛牛想知道，对于一个长度为 $\mathit N$ 的序列，如果他至多能删除 $\mathit N - 1$ 个数，请问他最少需要删除多少个数才能让序列的最大公约数变为 $\text 1$ ，或者这根本是不可能的

输入描述:

第一行输入一个整数，表示数据组数
对于每组数据，
第一行输入一个整数
接下来一行个整数表示序列中的数

输出描述:

输出T个整数，若可能，则输出最少需要删除的数，若不可能，则输出-1

示例1

输入

输出

-1
0

说明

对于第一个序列，可以证明，无论删除哪几个数，都无法使序列的gcd变为1
对于第二个序列，不需要删除

备注:

对于 $30 \%$ 的数据， $2 \leqslant N \leqslant 100$

对于 $100 \%$ 的数据， $T \leqslant 5, 2 \leqslant N \leqslant 10^5, 1 \leqslant 序列中的每个数 \leqslant 10^9$

算法知识视频讲解

寒冰-侠客

如果三个数字最大公约数是A，那么删除一个数字会让公约数A变小吗？

#include <bits/stdc++.h>//ASI
typedef long long ll;
using namespace std;
int n,t;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,x,y;
    cin>>t;
    while(t--)
    { /**< 如果序列最大公约数不是1，那么删除数字不可能让公约数变小 */
        cin>>n>>x;
        for(i=2;i<=n;i++)
        {
            cin>>y;
            x=__gcd(x,y);
        }
        if(x==1)
            cout<<0<<endl;
        else
            cout<<-1<<endl;
    }
    return 0;
}

发表于 2021-12-25 10:06:03 回复(0)