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

remove repeated lines

# | User | Rating |
---|---|---|

1 | tourist | 3682 |

2 | ecnerwala | 3603 |

3 | Benq | 3549 |

4 | Radewoosh | 3494 |

5 | Petr | 3452 |

6 | ksun48 | 3413 |

7 | maroonrk | 3406 |

8 | Miracle03 | 3314 |

9 | scott_wu | 3313 |

10 | Um_nik | 3299 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 214 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 177 |

7 | Ashishgup | 176 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 172 |

10 | -is-this-fft- | 169 |

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

remove repeated lines

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 23:51:38 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

"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

I think we have the same approach with different implementation way

GOT IT! thank you very much