into_the_world's blog

By into_the_world, history, 2 months ago, In English

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?

D — Factorial and Multiple

Submission

Thanks.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 2s? Let's count: 2 provides one 2. 4 provides two 2s. 6 provides one 2. 8 provides three 2s. Now we have (1+2+1+3 = 7) 2s. We still need one more. 10 provides one 2. Now we have eight 2s. 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.