FFT refers to Fast Fourier transform.

We are given 3 sets of integers A,B, and C, each consisting of n positive integers, and all integers are less than 5n. We are also given a target integer t and want to know if there are 3 elements iA,jB, and kC such that i+j+k=t. It is hard to get a better than n2 algorithm using naive methods. Show that using the FFT algorithm you can solve this problem in O(nlogn) time. [Hint: Start by associating a polynomial with each of the 3 given sets. For example, associate the polynomial iAxi with the set A.]