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≤105 positive integers, where each ai≤105 compute sum
∑1≤i<j≤nb(ai⋅aj)
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 dk=∑i,jbi⋅cj[i+j=k] If not, it's basically the same thing as a polynomial multiplication. If B(x)=b0+b1x+b2x2+...+bnxn, and C(x)=c0+c1x+c2x2+...+cnxn, then (B⋅C)(x)=d0+d1x+d2x2+...+d2nx2n
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 dk=∑i,jbi⋅cj[gcd(i,j)=k]
Algorithm to find GCD Convolution
Of course, we can compute it naively by iterating over all pairs of indicies. If b and c consists of n elements then the overall complexity would be O(n2log(max(b)+max(c))). But it turns out, that we can do better.
Let's look at the sum dk values, with indicies divisible by some integer g, so that is k=gm for some integer m. n/g∑m=1dgm=n/g∑m=1∑i,jbi⋅cj[gcd(i,j)=gm]=∑i,jbi⋅cj[g|gcd(i,j)]
From the definition of gcd, we know that g|gcd(i,j)⇔g|i∧g|j ∑i,jbi⋅cj[g|gcd(i,j)]=∑i,jbi⋅cj[g|i][g|j]= =∑i,j(bi[g|i])⋅(cj[g|j])=(∑g|ibi)(∑g|jcj)
We can define Bg=∑n/gm=1bgm, and Cg=∑n/gm=1cgm, and Dg=∑n/gm=1dgm. From above equation one could easily derive Dg=Bg⋅Cg. Knowing that O(n+n2+n3+...)=O(nlogn), arrays B and C can be computed directly from their definitions in O(nlogn).
Recovering a dk values from D array is simple. All we need is just subtract all the summands of Di except from the smallest. So, formally, we have dk=Dk−n/k∑m=2dkm Which can be computed using dynamic programming, starting from k=n.
So, the overall complexity of computing a GCD Convolution of two arrays of size n is O(nlogn).
Back to original problem
We can see, that b(ai⋅aj)=b(ai)⋅b(aj)gcd(b(ai),b(aj))2
So, having an array wb(ai)=∑ib(ai) all we need is just to compute a GCD Convolution of w with itself. Let's denote that convolution by d. Then, from definition ∑i,j:gcd(b(ai),b(aj))=kb(ai)⋅b(aj)gcd(b(ai),b(aj))2=dkk2
So answer to our problem is just a sum max(b(ai))∑k=1dkk2
If we denote A=max(ai) and B=max(b(ai)), then overall complexity of our solution is O(nlogA+BlogB)
Practice problems
Actually, I don't have any. I will be glad if you share some problems in comments. All I have is just this: