Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3496 |

3 | apiadu | 3438 |

4 | TLE | 3356 |

5 | LHiC | 3339 |

6 | mnbvmar | 3281 |

7 | 300iq | 3267 |

8 | Radewoosh | 3242 |

9 | yosupo | 3233 |

10 | 1919810 | 3203 |

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

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

4 | vovuh | 168 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 154 |

10 | rng_58 | 153 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2020 15:13:00 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If we replace each element of the array with all its divisors, then query for the maximum GCD is query on maximum element of subarray, that meets twice. For solve this problem we can use a technique similar to DQUERY.

We will solve this problem offline. First, create event of two type:

For generate query of first type we need factorize every elements of array $$$a$$$ and for every divisor $$$d$$$ remember index of element, that divide into $$$d$$$. This can be done with std::map.

Sort event first by $$$r$$$, than by type.

Iterate on event and if handle first type we need to do $$$C_l = max(C_l, d)$$$, if handle second type event we need to find $$$max(C_l, C_{l+1},...,C_r)$$$ — it's answer for $$$i$$$-th query. This can be done with data structure segment tree or BIT.

Calculate complexity. We factorize all elements of array $$$O(n \sqrt A)$$$, each divisor we update in map $$$O(n \sqrt[3] A \cdot log(n \sqrt[3] A)) $$$ and use segment tree for answer on query $$$O((q + n \sqrt[3] A)\cdot log(n))$$$.

Total complexity this solution is $$$O(n \sqrt A + n \sqrt[3] A \cdot log(n \sqrt[3] A) + q \cdot log(n))$$$. My solution work in 0.6 seconds.

Thanks a lot. Fortin

You can read editorial here https://discussed.codechef.com/questions/125148/gqr-editorial