#GYM104786A. John and Möbius Convolution
John and Möbius Convolution
Description
Today, John has found a sum and is looking to find a way to calculate it. He is given two arrays $a$ and $b$ of $n$ elements each. Calculate the following sum: $$ \sum_{i = 1}^{n} \sum_{j = 1}^{n} gcd(a_i, b_j) \cdot lcm(a_i, b_j) $$
* $gcd(x, y)$ is the greatest common divisor of $x$ and $y$
** $lcm(x, y)$ is the lowest common multiple of $x$ and $y$
The first line contains a single integer $n$ $(1 \leq n \leq 2 \cdot 10 ^ 5)$ - the number of elements in the array.
The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10 ^ 3)$
The third line contains $n$ integers $b_1, b_2, ..., b_n$ $(1 \leq b_i \leq 10 ^ 3)$
Ouput a single integer, the result of the sum.
Input
The first line contains a single integer $n$ $(1 \leq n \leq 2 \cdot 10 ^ 5)$ - the number of elements in the array.
The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10 ^ 3)$
The third line contains $n$ integers $b_1, b_2, ..., b_n$ $(1 \leq b_i \leq 10 ^ 3)$
Output
Ouput a single integer, the result of the sum.
2
2 6
3 12
120
Note
In this example, the answer is $gcd(2,3) \cdot lcm(2,3) + gcd(2,12) \cdot lcm(2,12) + gcd(6,3) \cdot lcm(6,3) + gcd(6,12) \cdot lcm(6,12) = 120$