题目链接

题目大意

有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足

$$c_k=\max_{\gcd(i,j)=k}|a_i-b_j|$$

$n \leq 10^5$

题解

我们先考虑拆绝对值：最后全部取反再做一遍就好了，式子变成了

$$c_k=\max_{\gcd(i,j)=k}a_i-b_j$$

发现我们只需要研究 $k=1$ 的情况就好了 其余的情况可以通过拿出含有这个因子的数来转化成是 $1$ 的情况 复杂度需要乘个调和级数。

我们把 $b$ 取反 题目变成了

$$ c_1=\max_{\gcd(i,j)=1} a_i+b_j \\=\max_{i=1}^n (a_i+\max_{\gcd(i,j)=1}b_j) $$

考虑我们枚举 $i$ 如何去计算 $\max_{\gcd(i,j)=1}b_j$：暴力枚举不太友好 我们看到 $gcd$ 就想到了$\mu$ ，但是这里是 max 不能 $mu$。

于是我们考虑二分最大的$b$，设为 $b'$，你需要检验

$$ \begin{align*} \max_{\gcd(i,j)=1}b_j \geq b' \\ sum_{j=1}^n [\gcd(i,j)=1][b_j \geq b'] > 0 \\ sum_{j=1}^n [b_j \geq b']\sum_{d|i,d|j}\mu(d) > 0 \\ sum_{d|i}\mu(d)\sum_{d|j}[b_j \geq b'] > 0 \end{align*} $$

我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。

时间复杂度 $O(nlog^3n)$ 欣慰的是这个题不卡常（最近被卡常题做晕了）

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
int n,A[MAXN],B[MAXN],C[MAXN];
int a[MAXN],b[MAXN],c[MAXN];
int q[MAXN],tr[MAXN];
int now,sm[MAXN];
std::vector<int> dec[MAXN];
bool p[MAXN];
int prime[MAXN],mu[MAXN],cnt;

inline void prework(){
    mu[1] = 1;
    FOR(i,2,MAXN-1){
        if(!p[i]) prime[++cnt] = i,mu[i] = -1;
        for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){
            p[i*prime[j]] = 1;mu[i*prime[j]] = -mu[i];
            if(!(i%prime[j])) {mu[i*prime[j]] = 0;break;}
        }
    }
    FOR(i,1,MAXN-1) for(int j = i;j < MAXN;j += i) dec[j].pb(i);
}

inline void work(int l,int r,int L,int R){
    if(l > r) return;
    if(L == R){
        FOR(i,l,r) c[q[i]] = L;
        return;
    }
    int mid = (L+R)>>1;
    while(now > mid){
        int x = tr[now--];
        for(auto i:dec[x]) ++sm[i];
    }
    while(now < mid){
        int x = tr[++now];
        for(auto i:dec[x]) --sm[i];
    }
    std::vector<int> toL,toR;
    FOR(i,l,r){
        int t = 0;
        for(auto d:dec[q[i]]) t += mu[d]*sm[d];
        if(t > 0) toR.pb(q[i]);
        else toL.pb(q[i]);
    }
    int tp = l-1,sz = toL.size();
    for(auto x:toL) q[++tp] = x;
    for(auto x:toR) q[++tp] = x;
    toL.clear();toR.clear();
    work(l,l+sz-1,L,mid);work(l+sz,r,mid+1,R);
}

inline int solve(int n){
    std::vector<int> S;now = n;
    FOR(i,1,n) S.pb(b[i]);std::iota(q+1,q+n+1,1);
    std::fill(sm+1,sm+n+1,0);std::sort(all(S));
    FOR(i,1,n){
        int x = std::upper_bound(all(S),b[i])-S.begin();
        tr[x] = i;
        S[x-1]++;
    }
    work(1,n,1,n);int ans = -1e9;
    FOR(i,1,n) ans = std::max(ans,a[i]+S[c[i]-1]-1);
    return ans;
}

inline void Solve(){
    FOR(i,1,n){
        for(int j = 1;j*i <= n;++j){
            a[j] = A[i*j];
            b[j] = B[i*j];
        }
        C[i] = std::max(C[i],solve(n/i));
//        exit(0);
    }
}

int main(){
    scanf("%d",&n);prework();
    FOR(i,1,n) scanf("%d",A+i);
    FOR(i,1,n) scanf("%d",B+i),B[i] = -B[i];
    Solve();
    FOR(i,1,n) A[i] = -A[i],B[i] = -B[i];
    Solve();
    FOR(i,1,n) printf("%d ",C[i]);
    return 0;
}