题解：CF2154C1 No Cost Too Great (Easy Version)

雄关漫道真如铁 · 2026-10-23 21:55:14 · 题解

题目链接：CF2154C1

题目大意

给定长度为 n 的正整数序列 a,b，保证 b_i=1。你可以进行任意次操作 a_i\leftarrow a_i+1，同时总代价增加 b_i。求使得存在正整数 i,j 满足 \gcd(a_i,a_j)>1 的最小总代价。

解决 t 次询问。

大致思路

考虑对每个数都进行质因数分解。那么，我们只要在遍历时发现某个质因数在前面出现过，则答案显然为 0。

而如果没有发现这种情况，方法也很简单，我们遍历每个位置，尝试对当前位置进行一次操作，然后对新的数同样质因数分解，看它是否与其他数有公因数即可。如果有，则答案为 1。我们并不需要考虑标记数组中当前位置原本的因数，因为 x,x+1 显然是互质的。

如果仍没有，由于只要随意选取两个奇数进行操作就必然能达成要求，则答案为 2。我们肯定能选择到两个奇数，因为如果只有一个奇数，答案应当为 0 或 1。如果没有奇数，答案应当为 0。

最终代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int MAXA=2e5+5;
int n,a[MAXN],b[MAXN];
bool cx[MAXA];
inline void dc()
{
    cin>>n;
    int maxa=0;
    for(int i=1;i<=n;i++) cin>>a[i],maxa=max(maxa,a[i]);
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=maxa+1;i++) cx[i]=false;
    for(int i=1;i<=n;i++)
    {
        int p=a[i];
        for(int j=2;j*j<=p;j++)
        {
            if(p%j==0)
            {
                if(cx[j])
                {
                    cout<<"0\n";
                    return;
                }
                cx[j]=true;
            }
            while(p%j==0) p/=j;
        }
        if(p>1&&cx[p])//一定要记得判 p>1
        {
            cout<<"0\n";
            return;
        }
        cx[p]=true;
    }
    for(int i=1;i<=n;i++)
    {
        int p=a[i]+1;
        for(int j=2;j*j<=p;j++)
        {
            if(p%j==0&&cx[j])
            {
                cout<<"1\n";
                return;
            }
            while(p%j==0) p/=j;
        }
        if(p>1&&cx[p])
        {
            cout<<"1\n";
            return;
        }
    }
    cout<<"2\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--) dc();
    return 0;
}

::cute-table |时间复杂度|空间复杂度| |:-:|:-:| |\mathcal{O}(tn\sqrt{\max a_i})|\mathcal{O}(n+\max a_i)|