in problem 27E you are asked to find the smallest positive integer which has exactly n divisors .

how to solve it > >

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

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

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

1 | adamant | 174 |

2 | awoo | 168 |

3 | nor | 165 |

4 | SecondThread | 164 |

5 | maroonrk | 162 |

5 | BledDest | 162 |

5 | Um_nik | 162 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

in problem 27E you are asked to find the smallest positive integer which has exactly n divisors .

how to solve it > >

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2023 14:51:38 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

We denote the number of divisors of a number

x, asd(x). It can be proven thatd(x) = (e_{1}+ 1)·(e_{2}+ 1)·...·(e_{k}+ 1) , wherex=p_{1}^{e1}·p_{2}^{e2}·...·p_{k}^{ek}is the prime factorization ofx.We notice that it's optimal for

p_{1}to be as small as it can be, so it should be equal to 2. We notice the same forp_{2}, so it should be equal to 3. It is optimal to take the smallest possible prime every time. So we should only take the firstkprimes. But consider the case wheree_{i}= 1i. We see that if we take more thanp_{k}= 41 (approximately), we are way over our limit of 10^{18}for our answer. So our list of primes should be up to 41.Now we try to construct the desired number by some kind of trial-and-error. As long as we can multiply our current number with the current prime raised to some power

e_{i}, we test for this situation, going to the next prime, knowing the current number's divisors and its value. Notice that every prime should not fit more than times in some numberX, and we only have about 15 primes, so operations aren't too much.Solution link: 43224863

thanks.. charis .. i got it...

trying every possibility in brute force way to get the minimum number...

ur solution is very clear... :))

You can bring down the operations even more, considering the fact that e(i)>=e(i+1) in the optimal solution.

Yes, you are right. Holding an extra parameter for

e_{i - 1}and startinge_{i}from there instead of 1. I believe you can also use dp on this idea if you modify it a little, but I don't think it's necessary.Fun fact: You missed 23 in your list of primes Luckily it didn't affect the solutions in this case :p