Lihmuf Balling
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2400
Tags: binary search, brute force, math

After working at a factory (Lihmuf Sorting), Lihmuf wants to play a game with his good friend, Pak Chanek. There are $$$N$$$ boxes numbered from $$$1$$$ to $$$N$$$. The $$$i$$$-th box contains $$$i$$$ balls. Pak Chanek and Lihmuf will play a game using those boxes.

There will be $$$N$$$ turns numbered from $$$1$$$ to $$$N$$$. On each turn, Pak Chanek chooses one box and takes all balls from that box, then Lihmuf does the same thing for one box he chooses (it is possible that the two chosen boxes are the same).

Given an integer $$$M$$$. Before the game begins, Lihmuf must choose an integer $$$K$$$ satisfying $$$1 \leq K \leq M$$$. It is known that on the $$$j$$$-th turn, Pak Chanek will choose the $$$j$$$-th box, while Lihmuf will choose the $$$y$$$-th box, with $$$y=((j \times K - 1) \bmod N) + 1$$$. Help Lihmuf choose the correct value of $$$K$$$ so that he will get as many balls as possible! If there are more than one possible values of $$$K$$$ that result in the maximum total balls, find the minimum such value of $$$K$$$.

Keep in mind that each box can be chosen more than once, but after a box is chosen for the first time, the box becomes empty.

Input format:
The only line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^9$$$; $$$1 \leq M \leq 2000$$$) — the number of boxes and the maximum limit for the value of $$$K$$$.

Output format:
An integer representing the value of $$$K$$$ that will make Lihmuf get as many balls as possible. If there are more than one possible value of $$$K$$$ that result in the maximum total balls, find the minimum such value of $$$K$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, if Lihmuf chooses $$$K=1$$$, the game will go as follows:

1. Pak Chanek chooses the $$$1$$$-st box and gets $$$1$$$ ball, then Lihmuf chooses the $$$1$$$-st box and gets $$$0$$$ balls.
2. Pak Chanek chooses the $$$2$$$-nd box and gets $$$2$$$ balls, then Lihmuf chooses the $$$2$$$-nd box and gets $$$0$$$ balls.
3. Pak Chanek chooses the $$$3$$$-rd box and gets $$$3$$$ balls, then Lihmuf chooses the $$$3$$$-rd box and gets $$$0$$$ balls.

In total, Lihmuf gets $$$0+0+0=0$$$ balls.

The maximum total balls that can be earned by Lihmuf is $$$0$$$ because he can only choose $$$K=1$$$. Therefore, $$$K=1$$$ is the minimum possible value of $$$K$$$ that results in the maximum total balls.

In the second example, if Lihmuf chooses $$$K=3$$$, the game will go as follows:

1. Pak Chanek chooses the $$$1$$$-st box and gets $$$1$$$ ball, then Lihmuf chooses the $$$3$$$-rd box and gets $$$3$$$ balls.
2. Pak Chanek chooses the $$$2$$$-nd box and gets $$$2$$$ balls, then Lihmuf chooses the $$$1$$$-st box and gets $$$0$$$ balls.
3. Pak Chanek chooses the $$$3$$$-rd box and gets $$$0$$$ balls, then Lihmuf chooses the $$$4$$$-th box and gets $$$4$$$ balls.
4. Pak Chanek chooses the $$$4$$$-th box and gets $$$0$$$ balls, then Lihmuf chooses the $$$2$$$-nd box and gets $$$0$$$ balls.
5. Pak Chanek chooses the $$$5$$$-th box and gets $$$5$$$ balls, then Lihmuf chooses the $$$5$$$-th box and gets $$$0$$$ balls.

In total, Lihmuf gets $$$3+0+4+0+0=7$$$ balls.

It can be obtained that $$$7$$$ is the maximum total balls that can be earned by Lihmuf. The possible values of $$$K$$$ that result in $$$7$$$ total balls are $$$3$$$ and $$$4$$$. Therefore, $$$K=3$$$ is the minimum possible value of $$$K$$$ that results in the maximum total balls.

Example input:
3 1

Example output:
1

Example input:
5 4

Example output:
3

Editorial:
To solve this, we just need to find the total number of balls Lihmuf will earn for each possible value of $$$K$$$ from $$$1$$$ to $$$M$$$.
If $$$K=1$$$, then Lihmuf gets $$$0$$$ balls.
If $$$K>1$$$ and $$$K$$$ is a factor of $$$N$$$, then Lihmuf will get all balls in the boxes with indices that are multiples of $$$K$$$.
If $$$K$$$ is not coprime to $$$N$$$, then Lihmuf can only possibly get the balls in the boxes with indices that are multiples of a factor of $$$N$$$ greater than $$$1$$$, which is already covered by the case above, so this is always not optimal.
Then, that leaves us with the case where $$$K>1$$$ and $$$K$$$ is coprime to $$$N$$$. Notice that in this case, Lihmuf will access each box exactly once.
For this case, consider the sequence of indices of the boxes accessed by Lihmuf. We can group this sequence into exactly $$$K$$$ groups, where each group consists of a sequence of indices $$$c$$$, $$$c+K$$$, $$$c+2K$$$, $$$c+3K$$$, and so on for some value $$$1\leq c\leq K$$$. For each group, while Lihmuf is accessing the boxes in the group, at the same time, Pak Chanek is accessing boxes $$$d$$$, $$$d+1$$$, $$$d+2$$$, $$$d+3$$$, and so on for some value $$$d$$$.
For this case, since $$$K>1$$$, that means at some point, Lihmuf will overtake Pak Chanek in the index of the box he accesses. That happens once $$$c+K\times p>d+p$$$ for some $$$p\geq0$$$. From that point on, Lihmuf will get all balls in the boxes he accesses in that group. The number of balls earned by Lihmuf in each group can be calculated in $$$O(1)$$$ using simple math and using the formula for the sum of an arithmetic sequence.
The total time complexity to calculate for a single value of $$$K$$$ is $$$O(K)$$$, so the total time complexity is $$$O(M^2)$$$.
Time complexity: $$$O(M^2)$$$