智能网站开发,公司网页介绍模板,温州大都市建设开发有限公司网站,域名备案购买互质 互质 互质 每次测试的时间限制#xff1a; 3 秒 每次测试的时间限制#xff1a;3 秒 每次测试的时间限制#xff1a;3秒 每次测试的内存限制#xff1a; 256 兆字节 每次测试的内存限制#xff1a;256 兆字节 每次测试的内存限制#xff1a;256兆字节 题目描述
给定… 互质 互质 互质 每次测试的时间限制 3 秒 每次测试的时间限制3 秒 每次测试的时间限制3秒 每次测试的内存限制 256 兆字节 每次测试的内存限制256 兆字节 每次测试的内存限制256兆字节 题目描述
给定一个由 n n n 个正整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 1 ≤ a i ≤ 1000 1 \le a_i \le 1000 1≤ai≤1000 ) 组成的数组。求 i j i j ij 的最大值使得 a i a_i ai 和 a j a_j aj 互质如果不存在这样的 i i i j j j输出 − 1 -1 −1 。
例如考虑数组 [ 1 , 3 , 5 , 2 , 4 , 7 , 7 ] [1, 3, 5, 2, 4, 7, 7] [1,3,5,2,4,7,7] 。由于 a 5 4 a_5 4 a54 和 a 7 7 a_7 7 a77 互质所以 i j i j ij 的最大值是 5 7 5 7 57 。
如果两个整数 p p p 和 q q q 的最大公因数是 1 1 1则这两个整数 p p p 和 q q q 是互质。 输入
输入由多个测试用例组成。第一行包含一个整数 t t t ( 1 ≤ t ≤ 10 1 \leq t \leq 10 1≤t≤10 ) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行包含一个整数 n n n ( 2 ≤ n ≤ 2 ⋅ 1 0 5 2 \leq n \leq 2\cdot10^5 2≤n≤2⋅105 ) - 数组的长度。
下一行包含 n n n 个空格分隔的正整数 a 1 a_1 a1 , a 2 a_2 a2 ,…, a n a_n an 1 ≤ a i ≤ 1000 1 \leq a_i \leq 1000 1≤ai≤1000 –数组的元素。( 1 ≤ a i ≤ 1000 1 \leq a_i \leq 1000 1≤ai≤1000 ) - 数组的元素。
保证所有测试用例的 n n n 之和不超过 2 ⋅ 1 0 5 2\cdot10^5 2⋅105 。 输出
对于每个测试用例输出一个整数-- i j i j ij 的最大值使得 i i i 和 j j j 满足 a i a_i ai 和 a j a_j aj 为共素数的条件或者在没有 i i i 、 j j j 满足条件的情况下输出 − 1 -1 −1 。 代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int INF 0x3f3f3f3f;
const int mod 1e9 7;
const int N 200010;int a[N];bool PD[1010][1010];int gcd(int a,int b)
{if(b0)return a;else return gcd(b,a%b);
}int main()
{for(int i1;i1000;i)for(int j1;j1000;j)if(gcd(i,j)1)PD[i][j]true;int t; cint;while (t--){int n; cinn;mapint,intmp;for(int i1;in;i){scanf(%d,a[i]);mp[a[i]]i; //mp用来记录每种数最后出现的位置} int ans-1;for(int i1;i1000;i)for(int ji;j1000;j)if(mp.count(i) mp.count(j))if(PD[i][j])ansmax(ans,mp[i]mp[j]);coutansendl;}return 0;
}解题思路如果枚举数组中的每一对数的话时间复杂度为 O ( n 2 ) O(n^2) O(n2) ,其中 n n n 为 2 ∗ 1 0 5 2*10^5 2∗105 该方案不可行这绝对会TLE。
这时我们可以发现 a [ i ] a[i] a[i] 的取值范围非常的小只有 1-1000 ,所以可以尝试枚举 1-1000 中选取 2 2 2 个数的所有组合然后判断每种组合在给定的数组中是否存在如果存在的话再判断它们是否互质如果互质的话找到这种组合中的两个数分别在给定的数组中最后出现的位置这可以通过一个map来存下数组中每种值最后出现的位置这种算法的时间复杂度为 O ( 100 0 2 ) O(1000^2) O(10002)
