题解 | #茕茕孑立之影#

茕茕孑立之影

https://ac.nowcoder.com/acm/contest/95323/A

题意:找出与数组中任意数互质的数,注意1不与任何数互质!

输入描述:每个测试文件均包含多组测试数据。第一行输入一个整数 T( 1 ≤ T ≤ 10^4) 代表数据组数,每组测试数据描述如下: 第一行输入一个整数 n ( 1 ≤ n ≤ 10^5 ) 代表数组元素个数.第二行输入 n 个整数 a1,a2,…,an ( 1 ≤ ai ≤ 10^9 )代表数组元素。除此之外,保证单个测试文件的 n 之和不超过 10^5.

法1:题中只要求任意一个数,可找出一个通解,即大于10的9次方的任意质数
#include<bits/stdc++.h>
using namespace std;

int main(){
    int t = 0, n = 0, a = 0, flag = 0;
    
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> n;
        
        for(int j = 0; j < n; j++){
            scanf("%d", &a);
            if(a == 1)flag = 1;
        }
        
        if(flag == 1)cout << "-1" <<endl;
        else cout << "1000000001" << endl;
        
        flag = 0;
    }
    
    return 0;
}

法2:找出最大公因数,并加1

(补充过程)

思路学习:当存在多种解时,尝试找特殊解/通解! !
全部评论

相关推荐

学一下吧现在太菜了:和简历没关系,你是清华的他就要了。多投投就行了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务