由于是做题时写的思路所以可能很乱 /kk

首先考虑 $k = 1$ 的情况。我们希望对于每一个 $i$ 求出一个 $j$ 使得 $\gcd(i,j) = 1,\max |a_i - b_j|$ 。

考虑把绝对值拆开，对于每个 $i$ 分别求最大的 $b_j$ 和最小的 $b_j$ 。这两个问题明显是对称的，考虑求最大的 $b_j$。

我们可以整体二分一下，比如当前二分的数为 $x$ ，把 $\ge x$ 的数的编号拿出来放到一个集合里面。我们预处理出每个编号的所有质因数 （$O(\log n)$ 级别的），对于每个编号，询问一下集合中有没有它的质因数的倍数。这些东西可以先把质因数提出来，不超过 $O(sz\log n\log n)$ 的询问，这里 $sz$ 是编号的个数。由于是编号的质因数，实际上个数是很少的（并起来更少），感觉 $sz$ 个数并起来也就 $O(sz)$ 个质因数。。

（这里其实是莫反过的）

如果 $k\neq 1$，实质上就是给所有 $k$ 的倍数的编号做一样的事情就行了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;

int pri[MAXN] , mu[MAXN] , en;
void sieve( ) {
	mu[1] = 1;
	for( int i = 2 ; i < MAXN ; ++ i ) {
		if( !pri[i] ) pri[++ en] = i , mu[i] = -1;
		for( int j = 1 ; j <= en && pri[j] * i < MAXN ; ++ j ) {
			pri[i * pri[j]] = 1;
			if( i % pri[j] == 0 ) { mu[i * pri[j]] = 0; break; }
			mu[i * pri[j]] = -mu[i];
		}
	}
}

int n , m;

int A[MAXN] , B[MAXN];

vi ps[MAXN];
vi a , b;

vi ques , bs;

int oc[MAXN];
int fuck( int l , int r , int op ) { // bs[l..r]
	if( ques.empty() ) return 0;
	int re = 0;
	if( l == r ) {
		for( int i : ques ) {
//			printf("%d %d\n",b[bs[l]],a[i]);
			re = max( re , abs( b[bs[l]] - a[i] ) );
		}
		return re;
	}
	int mid = l + r >> 1;
	if( op )
		rep( i , mid + 1 , r ) for( int x : ps[bs[i]] )
			++ oc[x];
	else
		rep( i , l , mid ) for( int x : ps[bs[i]] )
			++ oc[x];
	vi tmp1 , tmp2;
	for( int i : ques ) {
		ll fk = 0;
		for( int x : ps[i] )
			fk += oc[x] * mu[x];
		if( fk ) tmp1.pb( i );
		else tmp2.pb( i );
	}
	if( op )
		rep( i , mid + 1 , r ) for( int x : ps[bs[i]] )
			oc[x] = 0;
	else
		rep( i , l , mid ) for( int x : ps[bs[i]] )
			oc[x] = 0;
	ques = tmp1;
	if( op ) re = max( re , fuck( mid + 1 , r , op ) ) , ques = tmp2 , re = max( re , fuck( l , mid , op ) );
	else re = max( re , fuck( l , mid , op ) ) , ques = tmp2 , re = max( re , fuck( mid + 1 , r , op ) );
	return re;
}

int sol( ) { // solve k = 1 for vector a , b
	int n = a.size() - 1;
	bs.clear() , ques.clear();
	rep( i , 1 , n ) ques.pb( i ) , bs.pb( i );
	sort( all( bs ) , [&]( int i , int j ) { return b[i] < b[j]; } );
//	rep( i , 0 , n - 1 ) printf("%d ",bs[i]); puts("");
	int re = fuck( 0 , n - 1 , 0 );
	ques.clear();
	rep( i , 1 , n ) ques.pb( i );
	re = max( re , fuck( 0 , n - 1 , 1 ) );
	return re;
}

void solve() {
	sieve();
	cin >> n;
	rep( i , 1 , n ) scanf("%d",A + i);
	rep( i , 1 , n ) scanf("%d",B + i);
	for( int i = 1 ; i <= n ; ++ i )
		for( int j = i ; j <= n ; j += i )
			ps[j].pb( i );
	rep( i , 1 , n ) {
		a.clear() , b.clear();
		a.pb( 0 ) , b.pb( 0 );
		for( int j = i ; j <= n ; j += i ) a.pb( A[j] ) , b.pb( B[j] );
		printf("%d ",sol( ));
	}
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}