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. 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.
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Is there something that I said wrong? Why all the downvotes?
Why are you making a post about a TLE? The time complexity of your solution is $$$O(n^\frac{5}{4} log(n) log(max(a_i, b_i))$$$ Plugging values in, your code does around $$$1.5e9$$$ operations.
Why is there a $$$log(max(a_{i}, b_{i}))$$$?
there are at most 30 prime factors for a number ≤2⋅10^9
quoted from your blog.When doing time complexity analysis, you can't just say
I don't think that that would matter much
.Lets look at the bottleneck of the code.
We are doing $$$O(n)$$$ factors which is $$$O(n^{\frac{5}{4}}).$$$ Then, since there are at most 30 prime factors of a number $$$\le 2 \cdot 10^{9}$$$, the set which stores the union of the prime factors is at most $$$O(log(60))$$$. So I argue that the complexity is $$$O(n^{\frac{5}{4}} \cdot log(60))$$$
Oops. Actually the complexity is $$$O(n^\frac{5}{4} k \log(k))$$$ where $$$k$$$ is the maximum amount of prime factors a number can have. This is because you iterate over all prime factors of the pairs in each iteration. Evaluating with $$$k = 60$$$, this totals to $$$10^9$$$. Also, the constant factor of prime factorizing is probably somewhat high.
Why is it multiplied by $$$O(k)$$$?
This is because you iterate over all prime factors of the pairs in each iteration
If I use an
unordered_set
then I can remove the $$$O(log(60))$$$.for(auto& j: hld1) {
I think you doesn't need to use such a troublesome way to solve this problem... it can be much easier.
You can just first calculate the prime factor of the first pair and store it, then when you key in the other pairs, delete the prime factor that work to both numbers of the pair. Then, if there is no prime factor left, print
-1
, otherwise print the number.I know there are other people who use the algorithm and pass it, so maybe that's all the reason of all the downvotes...
Here I've just accepted this problem using this algorithm.
You can see my code here
I know of such a solution, but sometimes I want to try a new idea that I have not had before and try it out. This puzzles me as to why the program runs too slow. The complexity is as stated in the blog, and it should work for $$$n \le 150,000$$$.