Qualified's blog

By Qualified, history, 4 years ago, In English

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. 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.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there something that I said wrong? Why all the downvotes?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is there a $$$log(max(a_{i}, b_{i}))$$$?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Lets look at the bottleneck of the code.

          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))$$$

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Why is it multiplied by $$$O(k)$$$?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                This is because you iterate over all prime factors of the pairs in each iteration

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  If I use an unordered_set then I can remove the $$$O(log(60))$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  for(auto& j: hld1) {

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here I've just accepted this problem using this algorithm.

    You can see my code here

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.