Auto comment: topic has been updated by Duukh (previous revision, new revision, compare).

Auto comment: topic has been updated by Duukh (previous revision, new revision, compare).

I know the problem you are talking abt.

First notice that with $$$m = 2$$$ you get by the pigeonhole that at least half of them are there so $$$k \ge n / 2$$$. Now you can try randomized algo and check for $$$2$$$ elements in the array the probability of them being in the array maximizing $$$k$$$ is $$$\frac{1}{4}$$$ aka the probability of them not being both in that subarray is $$$\frac{3}{4}$$$ now if you repeat this like $$$n$$$ times the probability of not getting a good pair constituing the biggest sequence is $$$(\frac{3}{4})^n$$$ which goes to 0 you can do this experience $$$10$$$ times in practice and you are garanteed to get one. (a pair of elements both in the best sequence).

Now we have a pair $$$(a_i, a_j)$$$ that is present in the sequence what should we do? Well we know that $$$a_i \equiv a_j \pmod m \iff m \mid a_i - a_j$$$ you can try all divisors of $$$a_i - a_j$$$ let a divisor be $$$m$$$ all you need to know is to do an $$$\mathcal{O(n)}$$$ scan checking for each element $$$x$$$ in the array if $$$m \mid x - a_i$$$ (or $$$a_j$$$ they are equivalent obviously). and increment a counter. At the end you should have the longest sequence considering $$$a_i$$$ being in that sequence and $$$m$$$ as the mod.

Overall complexitiy $$$\mathcal{O(\text{number of tries} \cdot \sqrt{10^{12}}) \cdot n)}$$$ You may thing that it's too much but in fact it's a lot less that than, since we try for all divisors this is in practice way less than $$$\sqrt{10^{12}}$$$. And passes the tests if correctly implemented. Also one more must needed observation it's always optimal to check only prime divisors of $$$a_i - a_j$$$ (it's pretty obvious since if $$$p \mid m$$$ and $$$m \mid x - a_i$$$ then $$$p \mid x - a_i$$$) So you can see that it's really wayyyyyyy less than $$$\sqrt{10^{12}}$$$ scans