By LINKER_11, history, 2 months ago,

Hello everyone, can anyone tell me how to solve this problem (or how to solve this kind of problems) ?
remove repeated lines

• +21

 » 7 weeks ago, # | ← Rev. 3 →   +3 $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$ )
•  » » 7 weeks ago, # ^ |   +5 Amazing solution, I worked on another approach which seems like it's more optimizable somehow. It works as follows: Backtrack over all possible GCD values (so all values that have exactly 2k factors) 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". 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
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I think we have the same approach with different implementation way
•  » » 7 weeks ago, # ^ |   0 GOT IT! thank you very much