Yet Another Convolution

k가 1부터 n까지일 때 gcd(i, j) = k인 모든 쌍에 대해 |a_i - b_j|의 최댓값을 구해 출력한다.

어려움9정수론수학분할 정복정렬아직 제출이 없습니다시간 제한4초메모리 제한512 MB

문제 설명

예제1

You are given an integer array \(a_1, \dots , a_n\) and \(a_n\) integer array \(b_1, \dots , b_n\).

You have to calculate the array \(c_1, \dots , c_n\) defined as follows:

\[c_k = \max_{gcd(i,j)=k}{|a_i - b_j|}\text{.}\]

The first line of input contains a single integer \(n\) (\(1 \le n \le 10^5\)).

The second line of input contains \(n\) integers \(a_1, \dots , a_n\) (\(1 \le a_i \le 10^9\)).

The third line of input contains \(n\) integers \(b_1, \dots , b_n\) (\(1 \le b_i \le 10^9\)).

Output \(n\) integers \(c_1, \dots , c_n\).