题解：P14444 [ICPC 2025 Xi'an Practice] Great Indices

违规用户名1010570 · 2025-11-08 11:34:48 · 题解

P14444 [ICPC 2025 Xi'an Practice] Great Indices

水一发热身赛题解。

分析题意

找所有是至少是 n-1 个数倍数的下标。

分析做法

对于两个数 x,y 仅当 x\leq y 时 y 才有可能是 x 的倍数。

所以仅当当前的 a_i 为最大值或次大值时，a_i 才有可能为剩下 n 或 n-1 个数的倍数。

所以我们只需找到该序列的最大值与次大值，判断是否符合条件即可。

时间复杂度 O(n\log{n})，空间复杂度 O(n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
int a[300005];
vector<int> all;
signed main(){
    cin>>T;
    while(T--){
        all.clear();
        cin>>n;
        int maxx=-1,maxx2=-1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            maxx=max(maxx,a[i]);
        }
        for(int i=1;i<=n;i++){
            if(a[i]!=maxx){
                maxx2=max(maxx2,a[i]);
            }
        }
        int flag1=0,flag2=0;
        for(int i=1;i<=n;i++){
            if(maxx%a[i]!=0){
                flag1++;
            }
        }
        for(int i=1;i<=n;i++){
            if(maxx2%a[i]!=0){
                flag2++;
            }
        }
        if(flag1<=1){
            for(int i=1;i<=n;i++){
                if(a[i]==maxx){
                    all.push_back(i);
                }
            }
        }
        if(flag2<=1){
            for(int i=1;i<=n;i++){
                if(a[i]==maxx2){
                    all.push_back(i);
                }
            }
        }
        sort(all.begin(),all.end());
        cout<<all.size()<<"\n";
        for(int i=0;i<all.size();i++){
            cout<<all[i]<<" ";
        }
        cout<<"\n";
    }
}