CF2154C

DDF_ · 2025-11-11 12:35:45 · 题解

你说得对。但是无论什么代价都在所不惜。（题目名字）

题面

有一个长度为 n 的序列 a，对于每个位置 i，对其进行 +1 操作的代价是 b_{i}。求最小的代价，使得序列 a 中存在不互质的两个数。

对于这一题的简单版：b_{i}=1。

对于这一题的困难版：1 \le b_{i} \le 10^9。

题解

妙妙贪心思维题，从简单版开始想。

首先，特判本来已有一对不互质的数的情况。具体地，对于每个 a_{i} 对其分解质因数，然后开个桶 f_{x} 存质数 x 是否存在于 a 中，f_{x}=1 则 x 存在。若重复覆盖到一个点，则输出 0。

接着，对数列的性质进行观察：两个数 a_{i},a_{j} 均为奇数，则花费 b_{i}+b_{j} 代价将二者均 +1，使得其均为偶数。这便是答案的上界。若对两个及以上的数进行多次操作，明显不优于上述情况。

于是，对 b 排序。

此时只有对一个数进行操作的情况了。

在简单版中，很明显，一个数至多进行一次 +1 操作，对一个数进行大于 1 次 +1 显然不优于把两个数都进行一次 +1 的情况。具体地，从小到大枚举，对每个数 a_{i} 进行 +1 操作后分解质因数，同样若覆盖到 f_{x}=1 的地方，那么答案就为把这一个位置 +1 的代价，也就是 b_{i}。

困难版中，将一个数从 +1 一次推广到 +1 多次的情况：

• 对于 b_{i} 大于 b_{1}+b_{2} 的位置 i，对其进行操作肯定不优。
• 对于 b_{i} 大于 b_{1} 的位置 i，对其至多进行一次 +1 操作。证：b_{2} \ge b_{1} 且 b_{2} 是 \ge b_{1} 中最小的值，若 b_{i}>b_{1}，则有 b_{i} \ge b_{2}，因此 2 \times b_{i} \ge b_{2}+b_{1}。
• 对于 b_{i} 等于 b_{1} 的位置，可以进行多次操作。枚举所有 f_{x}=1 的 x，然后算使 a_{i} 变为 x 的倍数的最小代价。

做到这一步，你最终会发现：Time limit exceeded on test 23。

我想了一堆法子优化都被卡死了，这是算法出了问题！

仔细思考，就可以发现出题人可以构造一堆 b_{i}=b_{1} 卡掉。这种情况下怎么做呢？

构造了一堆 b_{i}=b_{1}……那么它不就退化到了类似简单版中，所有值均为 1 的情况了吗？！此时加两个的代价为 b_{1}+b_{2}= 2 \times b_{1}，只有对 b_{i} \le 2 \times b_{1} 的地方 +1 会更优！

把上面这个判掉，此时就只用判对第一个位置加多次了！

此题完结。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int _;
int n;
struct node {
    int a,id;
    int b;
} s[N];
int f[N];
int prime[N];
int minp[N],cnt;
int num,p[N];
int ct;
ll ans;
bool cmp(node x,node y) {
    return x.b<y.b;
}
inline int get() {
    char ch=getchar();
    int x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void solve() {
    ans=-1ll,ct=num=0;
    memset(f,0,sizeof f);
    n=get();
    for(int i=1;i<=n;i++) {
        s[i].a=get();
        if(~ans) continue;
        int x=s[i].a;
        if(x==1) continue;
        for(int j=minp[x];x>1;j=minp[x]) {
            if(x%j==0) {
                if(f[j]) {ans=0;break;}
                f[j]=1,p[++num]=j;
                while(x%j==0) x/=j;
            }
        }
    }
    for(int i=1;i<=n;i++) s[i].b=get();
    if(~ans) {puts("0");return;}
    sort(s+1,s+1+n,cmp),sort(p+1,p+1+num);
    ans=s[1].b+s[2].b;
    bool flag=false;
    for(int i=1;i<=n;i++) {
        if(s[i].b>ans) break;
        int x=s[i].a+1;
        for(int j=minp[x];x>1;j=minp[x]) {
            if(x%j==0) {
                while(x%j==0) x/=j;
                if(f[j]) {ans=s[i].b,flag=true;break;}
            }
        }
        if(flag) break;
    }
    if(s[2].b!=s[1].b) {
        for(int j=1;j<=num;j++) {
            if(s[1].a%p[j]==0) continue;
            ll x=p[j]-s[1].a%p[j];
            ans=min(ans,x*s[1].b);
            if(p[j]>s[1].a) break;
        }
    }
    printf("%lld\n",ans);
    return;
}
int main() {
    _=get();
    for(int i=2;i<=N-2;i++) {
        if(!minp[i]) prime[++cnt]=i,minp[i]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=N-2;j++) {
            minp[prime[j]*i]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
    while(_--) solve();
    return 0;
}