Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

[Tutorial] GCD Convolution

Revision en11, by szaranczuk, 2023-02-04 23:51:22

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 f(x) for any positive integer x as x divided by a greatest perfect square, that divides x.

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

Given an array a of n105 positive integers, where each ai105 compute sum

1i<jnf(aiaj)

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+j=kbicj 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 (BC)(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=gcd(i,j)=kbicj

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/gm=1dgm=n/gm=1gcd(i,j)=gmbicj=g|gcd(i,j)bicj

From the definition of gcd, we know that g|gcd(i,j)g|ig|j g|gcd(i,j)bicj=i,jbicj[g|gcd(i,j)]=i,jbicj[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=BgCg. 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 for the smallest. So, formally, we have dk=Dkn/km=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 f(aiaj)=f(ai)f(aj)gcd(f(ai),f(aj))2

So, having an array wf(ai)=if(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(f(ai),f(aj))=kf(ai)f(aj)gcd(f(ai),f(aj))2=dkk2

So answer to our problem is just a sum max(f(ai))k=1dkk2

If we denote A=max(ai) and F=max(f(ai)), then overall complexity of our solution is O(nlogA+FlogF)

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:

Tags number theory, gcd, convolution, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English szaranczuk 2023-02-05 16:37:54 33
en15 English szaranczuk 2023-02-05 01:19:42 0 (published)
en14 English szaranczuk 2023-02-05 01:17:32 108
en13 English szaranczuk 2023-02-05 01:01:55 653
en12 English szaranczuk 2023-02-05 00:10:36 15
en11 English szaranczuk 2023-02-04 23:51:22 151
en10 English szaranczuk 2023-02-04 23:37:19 54
en9 English szaranczuk 2023-02-04 23:33:55 7
en8 English szaranczuk 2023-02-04 23:31:29 118
en7 English szaranczuk 2023-02-04 22:50:30 340
en6 English szaranczuk 2023-02-04 22:44:31 682
en5 English szaranczuk 2023-02-04 22:15:46 1037
en4 English szaranczuk 2023-02-04 21:39:05 627
en3 English szaranczuk 2023-02-04 21:18:33 233
en2 English szaranczuk 2023-02-04 21:06:12 325
en1 English szaranczuk 2023-02-04 20:59:01 1344 Initial revision (saved to drafts)