In yesterday's AtCoder Beginner Contest 280 I didn't able to solve D. Then I was looking for solution and after seeing this submission I was shocked. Can anyone tell me how the logic work for this problem submission?

Thanks.

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

1 | tourist | 3803 |

2 | Benq | 3783 |

3 | Radewoosh | 3602 |

4 | maroonrk | 3575 |

5 | fantasy | 3526 |

6 | ko_osaga | 3500 |

7 | ksun48 | 3491 |

8 | Um_nik | 3486 |

9 | jiangly | 3474 |

10 | orzdevinwang | 3461 |

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

1 | awoo | 180 |

2 | -is-this-fft- | 177 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 161 |

8 | kostka | 160 |

9 | YouKn0wWho | 158 |

10 | errorgorn | 153 |

In yesterday's AtCoder Beginner Contest 280 I didn't able to solve D. Then I was looking for solution and after seeing this submission I was shocked. Can anyone tell me how the logic work for this problem submission?

Thanks.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/06/2023 02:36:16 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Suppose $$$k$$$ is a prime, then, the answer is always $$$k$$$. If $$$k$$$ is composite, remember that if a divisor an integer $$$n$$$ is less than or equal to $$$\sqrt{n}$$$, the other divisor is greater than or equal to $$$\sqrt{n}$$$. The solution uses that idea.

The limit is $$$2 \cdot 10^{6}$$$, you can get a better limit by figuring out the last prime smaller than $$$10^{6}$$$(which is $$$999983$$$) and multiply by $$$2$$$. Why multiply by $$$2$$$? Because we can get a square of that prime as an input for $$$k$$$(which means that the answer would be $$$prime * 2$$$). Check the answer for $$$k = 1999966$$$ with $$$limit = 10^{6}$$$ to get what I mean and why the limit should be at least $$$1999966$$$.

Thanks.

Here is an alternative approach. Suppose

`k`

is`1792`

. Convert`1792`

into`2^8 * 7^1`

. It is clear that`n`

needs to be at least`7`

in order to cover the`7`

, but what is the`n`

required to provide eight`2`

s? Let's count:`2`

provides one`2`

.`4`

provides two`2`

s.`6`

provides one`2`

.`8`

provides three`2`

s. Now we have (`1+2+1+3 = 7`

)`2`

s. We still need one more.`10`

provides one`2`

. Now we have eight`2`

s. This means`n==10`

is the max n needed. The other factor found earlier is`n==7`

but`7`

is less than`10`

. So, the answer is`10`

.Edit: Just realized OP was referring to a particular submission.

Thanks.