#P9671. Yet Another Convolution

    ID: 6299 传统题 6000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-并行二分莫比乌斯反演倍数枚举线性筛杂项

Yet Another Convolution

题目描述

给定数组 a,ba,b,求出数组 cc,满足:

ck=max⁡gcd⁡(i,j)=k∣ai−bj∣c_k=\max_{\gcd(i,j)=k}|a_i-b_j|

输入格式

第一行一个整数 nn。

接下来一行 nn 个整数 aia_i。

接下来一行 nn 个整数 bib_i。

输出格式

输出一行 nn 个整数 cic_i。

样例

8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
7 5 3 3 1 3 5 7

数据范围

对于全部数据,1≤n≤1051\le n\le 10^5,1≤ai,bi≤1091\le a_i,b_i\le 10^9。