上海计算机学会2026年2月月赛C++丙组T3 Primary Pair

长春高老师编程

308人浏览 · 2026-04-01 16:03:18

长春高老师编程 · 2026-04-01 16:03:18 发布

Primary Pair

题目描述

冰棍很喜欢高级的东西，他也觉得一些数学性质很"高级"。

冰棍有一个长为 n 的序列 ${a_i\}$ 。他认为如果 $a_i$ 和 $a_j$ 互质，那么 $(i, j)$ 是一个高级数对。他想知道所有高级数对中的 $i + j$ 最大是多少。

输入格式

输入第一行一个整数 T。

接下来 T 组数据，每组第一行一个数 n。

接下来一行 n 个空格分隔的正整数 $a_i$ 。

输出格式

对于每组测试数据，输出一个整数，为满足条件的最大 $i + j$ 。若不存在符合条件的 $i, j$ 则输出 $- 1$ 。

数据范围

对于 $60%60\%$ 的数据， $\le 100$ 。
对于 $100%100\%$ 的数据， $\le T \le 10$ ， $\le n \le 2 \cdot 10^5$ ， $\le a_i \le 1000$ 。

样例

样例 1

输入：

6
3
3 2 1
7
1 3 5 2 4 7 7
5
1 2 3 4 5
3
2 2 4
6
5 4 3 15 12 16
5
1 2 2 3 6

输出：

Primary Pair 题解

我的解题思路

我看到这道题的核心要求是：找到互质的数对，让它们的下标之和最大。而且数据范围很关键：数组长度最大 2e5，但数字大小最多只有 1000。

我是这么思考的：

数组很长，但数值很小，我不需要遍历所有数对，那样会超时。
我只需要记录每个数字最后出现的下标，因为下标越大，加起来的和就越大，这是最优的。
最后我只需要在 1~1000 这些数字里暴力枚举所有数对，判断是否互质，然后取最大下标和就行。

我的代码思路与逐行说明

我写的这段代码非常简洁高效，完全符合题目要求，下面是我的思路：

#include <bits/stdc++.h>
using namespace std;
int t,n,x;
int p[1005];  // 我用 p 数组存每个数字最后出现的下标，最多 1000
int main() {    
    cin>>t;    // 我读入测试数据组数
    while(t--){  // 每组数据循环处理
        cin>>n;
        memset(p,0,sizeof(p));  // 每次清空数组，避免上一组数据影响
        
        for(int i=1;i<=n;i++){  // 我遍历数组，记录每个数最后出现的下标
            cin>>x;
            p[x]=max(p[x],i);  // 只保留最大（最后）的下标，这是最优的
        }
        
        int ans=-1;  // 答案初始化为 -1，表示没有找到
        
        // 我暴力枚举 1~1000 所有数对
        for(int i=1;i<=1000;i++){
            for(int j=1;j<=1000;j++){
                if (p[i]==0||p[j]==0) continue;  // 没出现过的数字直接跳过
                if (__gcd(i,j)==1){  // 判断互质
                    ans=max(ans,p[i]+p[j]);  // 更新最大下标和
                }
            }
        }
        
        cout<<ans<<"\n";
    }
    return 0;
}