CF1973F Maximum GCD Sum Queries 题解

题目链接

点击打开链接

题目解法

首先想到枚举两个数列的 $\gcd $，求最小代价
两个数列的 \(\gcd\) 应该分别是 \(a_1,b_1\) 的因数 或 \(b_1,a_1\) 的因数
这样就把枚举范围缩小到了 \(d(a_1)\times d(b_1)\)，这求最小代价需要 \(O(n)\)，不够快

假设枚举的 \(\gcd\) 分别为 \(x,y\)
它可以产生合法解当且仅当：\(\forall i\in [2,n]\;(a_i\%x=0\) 且 \(b_i\%y=0)\) 或 \((a_i\%y=0\) 且 \(b_i\%x=0)\)
会产生 \(c_i\) 代价的数对 \((a_i,b_i)\) 需要满足：

1. 不满足 \(a_i\%x=0\) 且 \(b_i\%y=0\)
2. 满足 \(a_i\%y=0\) 且 \(b_i\%x=0\)

我们考虑一组 \((a_i,b_i)\) 对 \(x,y\) 的贡献，发现产生合法解和计算 \(c\) 都可以拆成若干数的因数加一个值
这可以做高维前缀和
后面的步骤就显然了

时间复杂度 \(O(d(V)d(V)\omega(V))\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
typedef vector<int> vi;
const int N=500010;
int n,q,a[N],b[N],c[N],id[N],ans[N];
LL qry[N];
vector<pii> cmb;
vi f;vector<LL> g;
int ind(int x,int y){ return lower_bound(cmb.begin(),cmb.end(),pair{x,y})-cmb.begin();}
vi get_div(int x){
    vi ret;
    for(int i=1;i*i<=x;i++) if(x%i==0){
        ret.pb(i);
        if(i!=x/i) ret.pb(x/i);
    }
    return ret;
}
vi get_pr(int x){
    vi ret;
    for(int i=2;i*i<=x;i++) if(x%i==0){
        ret.pb(i);
        while(x%i==0) x/=i;
    }
    if(x>1) ret.pb(x);
    return ret;
}
#define fi first
#define se second
typedef pair<LL,int> pli;
vector<pli> cost;
int main(){
    read(n),read(q);
    F(i,1,n) read(a[i]);
    F(i,1,n) read(b[i]);
    F(i,1,n) read(c[i]);
    F(i,1,q) read(qry[i]),id[i]=i;
    sort(id+1,id+q+1,[&](int x,int y){ return qry[x]<qry[y];});
    vi d1=get_div(a[1]),d2=get_div(b[1]);
    int tot=d1.size()*d2.size();
    f.resize(tot),g.resize(tot);
    F(o,0,1){
        cmb.clear();
        for(int x:d1) for(int y:d2) cmb.pb({x,y});
        sort(cmb.begin(),cmb.end());
        F(i,0,tot-1) f[i]=g[i]=0;
        F(i,2,n){
            int A1=gcd(a[1],a[i]),B1=gcd(b[1],b[i]);
            int A2=gcd(a[1],b[i]),B2=gcd(b[1],a[i]);
            f[ind(A1,B1)]++,f[ind(A2,B2)]++,f[ind(gcd(A1,A2),gcd(B1,B2))]--;
            g[ind(A2,B2)]+=c[i],g[ind(gcd(A1,A2),gcd(B1,B2))]-=c[i];
        }
        vi prm=get_pr(a[1]);
        for(int pr:prm){
            int j=tot-1;
            DF(i,tot-1,0) if(cmb[i].fi%pr==0){
                while(cmb[j]!=pair{cmb[i].fi/pr,cmb[i].se}) j--;
                f[j]+=f[i],g[j]+=g[i];
            }
        }
        prm=get_pr(b[1]);
        for(int pr:prm){
            int j=tot-1;
            DF(i,tot-1,0) if(cmb[i].se%pr==0){
                while(cmb[j]!=pair{cmb[i].fi,cmb[i].se/pr}) j--;
                f[j]+=f[i],g[j]+=g[i];
            }
        }
        F(i,0,tot-1) if(f[i]==n-1) cost.pb({g[i]+o*c[1],cmb[i].fi+cmb[i].se});
        swap(d1,d2),swap(a[1],b[1]);
    }
    sort(cost.begin(),cost.end());
    int val=0,curp=1;
    for(auto [c,v]:cost){
        while(curp<=q&&qry[id[curp]]<c) ans[id[curp]]=val,curp++;
        chkmax(val,v);
    }
    while(curp<=q) ans[id[curp]]=val,curp++;
    F(i,1,q) printf("%d ",ans[i]);puts("");
    return 0;
}