Why is this code getting TLE?

Revision en6, by Qualified, 2020-11-14 06:16:25

Here is the problem.

Code

The factorization algorithm is taken from KACTL, same with the Miller-Rabin and the modmul and the modpow.

My thought process:

If we take each pair and then prime factorize each of the numbers in the pair and then take the union of those prime factors and then for each union, we count the number of primes and if there are $$$n$$$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.

Complexity

Since the prime factorization is $$$O(n^{\frac{1}{4}})$$$, and we are doing $$$O(n)$$$ of them and there are at most 30 prime factors for a number $$$\le 2 \cdot 10^{9}$$$, the complexity is about $$$O(n \cdot n^{\frac{1}{4}})$$$ or $$$O(n^{\frac{5}{4}})$$$. Also, I didn't add in the set's insert which works in $$$O(log(n))$$$, but I don't think that that would matter much. This complexity should suffice for $$$n \le 150,000$$$

Please let me know if there is a section where it is not clear. Thanks for reading the blog.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Qualified 2020-11-14 15:49:38 7 Tiny change: 'n the pair and then take t' -> 'n the pair. Then take t'
en6 English Qualified 2020-11-14 06:16:25 114
en5 English Qualified 2020-11-14 06:15:16 73
en4 English Qualified 2020-11-14 06:08:38 6
en3 English Qualified 2020-11-14 06:08:12 18
en2 English Qualified 2020-11-14 06:07:37 306 Tiny change: 'c{1}{4}})$.\n\nPle' -> 'c{1}{4}})$ or $O(n^(\frac{5}{4}))$.\n\nPle'
en1 English Qualified 2020-11-14 06:01:15 3727 Initial revision (published)