you need to be in control. you are in control when you keep the first player in "loop". if you take number of buttons is 6, say, then the "loop" length is 3, i.e. if you take max number of buttons as 3 - 1 = 2, then whatever amount the first player takes you can keep them in loop. if they take first time 1, you take 2 - in sum 3, 3 - remaining, you are a winner. if they take 2 - you take 1, 3 remaining again - you are a winner.
so, idea is to find the smallest divisor of a number > 2 & answer will be that - 1. hope that makes sense.

Edited by author 18.01.2019 19:50

WLOG, let's break `k` elements of heap into block of length `d`. The numbers below are listed from 1, ..., k in their congruent modulo of `d`.
[1, 2, ...., (d - 1), d], [1, 2, ...., (d - 1), d], ......(k / d) blocks. Here [..] is a block notation. B = #blocks of length `d` = (k / d)

Basis: If B = 1, it's always true, as `first player` can pick whatever from 1, ..., (d - 1), `second player` always left with atleast 1 element by less then d to be picked. So `second player` player will greedily pick all remaining element in the block as an optimal move for his/her winning.

Hypothesis: Let say it's true upto (B - 1) blocks that `second player` has taken the last element.

Proof:
If we have B block then since it is true for (B - 1) blocks we left with 1 block of element to pick and since `first player` is the who pick first in the last 1 block by using the `basis` we know that `second player` is always the winner. Hence, if we take the divisor of number of elements in the heap (k) we always end of with `second player` being the winner.

Edited by author 07.06.2022 10:23

Edited by author 07.06.2022 10:23

 for j := 3 to sqrt(n) do  will help you :)

wtf i=k / 3; ??

If k%(l+1)==0 then 2nd have a chance to win.
And 1st wins if k%(l+1)!=0

try it: for (l=3;k%l!=0;l++);;

Edited by author 31.03.2017 14:34

thnx man .. that should help

5 years later, same trap grabbing me :(

No. Because we know that if k=3 then answer 2. So we can remove 3 buttons from bunch. And find answer for k=4, but answer for this input will be 3. So 2!=3 and such answer is wrong. So answer will be 6 (cause we can't divide it on groups answer for those we know).

it isn't the smallest

I think one can get AC in 0.001 by giving solutions that have precalculated values for K = 3...10^8.

They use sqrt

Numbers are read from stdin

I think your j should be n div 2,and I promise it's not TLE.And you can define 'ans' to store the answer and let it equal n.That's all.

zj_zcy, what if n = 3 ?
Your program wrote 0, but right answer 2

The trouble is if n is big prime.
Try this:
99999989
The answer is:
99999988.

Think how to modify algorithm to catch big primes in factorization. Here it isn't necessary, but it will be useful.

Your code will possibly fail for integers like 2*n,also for test cases where n is a prime number

I made the same, but WA on test 11. What's the matter?
I see a solution in another topic, there used I64. Oh, don't tell me to use I64. 10^8 is involved to int.
Why does not it work?

<code>
#include <stdio.h>

int K;
int L;

int main()
{
    scanf("%d", &K);
    L = 2;
    while (K%(L+1) != 0)
    {
        if ((L+1)*(L+1) > K)
        {
            printf("%d\n", K-1);
            return 0;
        }
        L++;
    }

    printf("%d\n", L);
    return 0;
}
</code>

Edited by author 18.08.2011 03:22

"l<100000000"
Indeed, why?

I think so.
Because N-1 could always be the right answer,but I don't know why I got wa #11

So fabulous.

Explain this solution, please.
I'm a beginning programmer, so I can't understand.