# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### Codeforces [Gym 102354B] Yet Another Convolution

posted on 2020-03-25 12:37:45 | under 题解 |

$$b_k,b_{2k},b_{3k}\cdots b_{pk}$$

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

const int N = 300010 ;

#define p_b push_back
#define upb upper_bound

void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ;  cout << c ;
}

int n ;
int xq ;
int cnt ;
int q[N] ;
int A[N] ;
int B[N] ;
int lq[N] ;
int rq[N] ;
int pr[N] ;
int ta[N] ;
int tb[N] ;
int Mu[N] ;
int sum[N] ;
int res[N] ;
int ans[N] ;
int tmp[N] ;
int base[N] ;
bool vis[N] ;
vector <int> d[N] ;

int p = d[x].size() ;
for (int i = 0 ; i < p ; ++ i)
sum[d[x][i]] += y ;
return ;
}
void upd(int x){
while (xq > x) add(base[-- xq], 1) ;
while (x > xq) add(base[xq ++], -1) ;
//debug(sum, 1, 50, '\n') ;
}
int calc(int x){
int ret = 0 ;
int p = d[x].size() ;
for (int i = 0 ; i < p ; ++ i)
ret += Mu[d[x][i]] * sum[d[x][i]] ;
return ret ;
}
void do_it(int l, int r, int vl, int vr){
if (l > r) return ;
if (vl == vr){
for (int i = l ; i <= r ; ++ i)
ans[q[i]] = vl ; return void() ;
}
int vmid = (vl + vr) >> 1 ;
int tl = 0, tr = 0 ; upd(vmid + 1) ;
for (int i = l ; i <= r ; ++ i){
if (calc(q[i]) <= 0)
lq[++ tl] = q[i] ;
else rq[++ tr] = q[i] ;
}
//cout << tl << " " << tr << endl ;
for (int i = 1 ; i <= tl ; ++ i) q[l + i - 1] = lq[i] ;
for (int i = 1 ; i <= tr ; ++ i) q[l + tl + i - 1] = rq[i] ;
do_it(l, l + tl - 1, vl, vmid) ; do_it(l + tl, r, vmid + 1, vr) ;
}
int do_do(int k){
for (int i = 1 ; i <= k ; ++ i)
tmp[q[i] = i] = tb[i], sum[i] = 0 ;
sort(tmp + 1, tmp + k + 1) ; int x ; xq = k + 1 ;
for (int i = 1 ; i <= k ; ++ i){
x = upb(tmp + 1, tmp + k + 1, tb[i]) - tmp ;
x -- ; base[x] = i ; tmp[x] ++ ;
}
int ret = -2333333 ; do_it(1, k, 1, k) ; //debug(q, 1, k, '\n') ;
for (int i = 1 ; i <= k ; ++ i)
ret = max(ret, ta[i] + tmp[ans[i]] - 1) ;
return ret ;
}
void solve(){
for (int i = 1 ; i <= n ; ++ i){
for (int j = 1 ; i * j <= n ; ++ j)
ta[j] = A[i * j], tb[j] = B[i * j] ;
res[i] = max(res[i], do_do(n / i)) ;
}
}
void sieve(int k){
vis[0] = vis[1] = Mu[1] = 1 ;
for (int i = 2 ; i <= k ; ++ i){
if (!vis[i])
pr[++ cnt] = i, Mu[i] = -1 ;
for (int j = 1 ; j <= cnt ; ++ j){
if (pr[j] * i > k) break ;
vis[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
Mu[i * pr[j]] = - Mu[i] ;
}
}
for (int i = 1 ; i <= k ; ++ i)
for (int j = 1 ; i * j <= k ; ++ j)
d[i * j].p_b(i) ;
}
int main(){
sieve(N - 10) ;
ios :: sync_with_stdio(false) ;
cin.tie(0) ; cout.tie(0) ; cin >> n ;
for (int i = 1 ; i <= n ; ++ i) cin >> A[i] ;
for (int i = 1 ; i <= n ; ++ i) cin >> B[i] ;
for (int i = 1 ; i <= n ; ++ i) B[i] = -B[i] ;
solve() ;
//for (int i = 1 ; i <= n ; ++ i)
//    cout << res[i] << " \n"[i == n] ;
for (int i = 1 ; i <= n ; ++ i)
A[i] = -A[i], B[i] = -B[i] ;
solve() ;
for (int i = 1 ; i <= n ; ++ i)
cout << res[i] << " \n"[i == n] ;
return 0 ;
}