On today's POI training camp round I have learnt a nice technique that could possibly be useful in some number theory problems. I couldn't find any CF article on it, so I think it's fair enough to share it on my own.

Remark on used notation

In some sums I will use an Iverson notation

Problem: Squarefree Function

Let's define a Squarefree Function $$$b(x)$$$ for any positive integer $$$x$$$ as $$$x$$$ divided by a greatest perfect square, that divides $$$x$$$.

For example: $$$b(1) = 1$$$, $$$b(2) = 2$$$, $$$b(4) = 1$$$, $$$b(6) = 6$$$, $$$b(27) = 3$$$, $$$b(54) = 6$$$, $$$b(800) = 2$$$

Given an array $$$a$$$ of $$$n \leq 10^5$$$ positive integers, where each $$$a_i \leq 10^5$$$ compute sum

\begin{gather} \sum\limits_{1 \leq i < j \leq n}b(a_i\cdot a_j) \end{gather}

Technique: GCD Convolution

You might probably heard about a Sum Convolution. For two arrays $$$b$$$, and $$$c$$$, it is defined as an array $$$d$$$ such that \begin{gather} d_k = \sum\limits_{i,j}b_i\cdot c_j[i + j = k] \end{gather} If not, it's basically the same thing as a polynomial multiplication. If $$$B(x) = b_0 + b_1x + b_2x^2 + ... + b_nx^n$$$, and $$$C(x) = c_0 + c_1x + c_2x^2 + ... + c_mx^m$$$, then $$$(B \cdot C)(x) = d_0 + d_1x + d_2x^2 + ... + d_{n+m}x^{n+m}$$$

Let's define GCD Convolution by analogy

Definition

A GCD Convolution of two arrays $$$b$$$, and $$$c$$$, consisting of positive integers, is an array $$$d$$$ such that \begin{gather} d_k = \sum\limits_{i, j}b_i\cdot c_j[gcd(i,j) = k] \end{gather}

Algorithm to find GCD Convolution

Of course, we can compute it naively by iterating over all pairs of indicies. If size of $$$b$$$ is $$$n$$$, and size of $$$c$$$ is $$$m$$$, the overall complexity would be $$$O(nmlog(max(b) + max(c)))$$$. But it turns out, that we could do better.