KNOW_ME_IF_YOU_CAN's blog

ECPC Problem A) GCDHBD
By KNOW_ME_IF_YOU_CAN, history, 4 years ago, In English

Hello everyone, can anyone tell me how to solve this problem (or how to solve this kind of problems) ? Screenshot-from-2021-02-19-22-08-35
remove repeated lines

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

$$$gcd(x,y)$$$ equals to the multiplication of all the common factors between $$$x$$$ and $$$y$$$.

$$$gcdHBD(x,y)$$$ equals to the multiplication of the first $$$k$$$ factors of $$$x$$$ and the last $$$k$$$ factors of $$$y$$$ .

so $$$gcd(x,y)$$$ = $$$gcdHBD(x,y)$$$ iff the first $$$k$$$ factors of $$$x$$$ are common factors in $$$y$$$ and the last $$$k$$$ factors of $$$y$$$ are common in $$$x$$$.

so $$$x$$$ and $$$y$$$ should have at least $$$2k$$$ factors.

now let's get the maximum value of $$$k$$$ in the worst case: $$$gcd(x,y)$$$ <= $$$n$$$ and $$$n<=10^5$$$ in the worst case all the factors will be equals to $$$2$$$. so $$$k$$$ <= $$$log2(10^5)/2$$$ , $$$k$$$ <= $$$8$$$.

so if $$$k$$$ > $$$8$$$ the answer is $$$0$$$.

so what to do if $$$k$$$ <= $$$8$$$ ?

for each integer $$$x$$$ $$$[1,n]$$$
1- get it's factors.

2- remove the first $$$k$$$ factors from it ( that are common in $$$x$$$ and $$$y$$$ )

3- backtrack in these remaning factors to get the last $$$k$$$ factors ( that are common in $$$x$$$ and $$$y$$$ ).

4- make another backtrack to get another factors that are not in $$$x$$$ so can't affect the $$$gcd$$$ ( on primes from $$$2$$$ to $$$r$$$ where $$$r$$$ is the lowest factor in $$$y$$$ )

code : https://ideone.com/61h70N

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Amazing solution, I worked on another approach which seems like it's more optimizable somehow. It works as follows:

    1. Backtrack over all possible GCD values (so all values that have exactly 2k factors)
    2. For each $$$g$$$, backtrack over all $$$x$$$ that have the lower $$$k$$$ factors same as the lower $$$k$$$ factors in $$$g$$$, and divides $$$g$$$. Mark any taken factor as "bad".
    3. For each $$$x$$$, backtrack over all $$$y$$$ that have upper $$$k$$$ factors same as upper $$$k$$$ factors in $$$g$$$, divides $$$g$$$, and has no "bad" factors.

    "bad" factors ensures that besides $$$g$$$, there are no extra common factors between $$$x$$$, and $$$y$$$.

    Intuitively, it seems the third backtracking does a lot of repeated work for many $$$x$$$, so this is where I see the improvement.

    I haven't been able to prove the complexity, but it passes my trivial stress test.

    https://ideone.com/4lgcAd

    → Reply