Anyone please elaborate the problem. Thanks in Advance.

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

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

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

1 | 1-gon | 215 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | Ashishgup | 169 |

Anyone please elaborate the problem. Thanks in Advance.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2021 03:04:55 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let's solve the problem for each prime factor

pseparately.Suppose LCM of two numbers

iandjhasp^{e}in its factorization, then at least one of them must havep^{e}in its factorization as well. There are (e+ 1)^{2}-e^{2}ways to choose the exponents ofpso that one of the numbers has exponenteand the other one has exponent at moste.First let's make a list of primes with a sieve, then solve the problem for each prime factor as explained above. The results have to be multiplied because each prime factor is independent.

We'll be counting all pairs twice, except the case when

i=j(whennis a perfect square), so if the answer calculated isresthen will do the trick.