来自"NOCOW"

这是一道经典的博弈的题目，首先我们想如果给定了k,l那么怎么确定第一个人是不是必胜的，如果是的那他第一次应该取几个？ 显然是 k mod (l+1) 个 ，如果 k mod (l+1)=0那么显然是必输的。

我们这样看，第一个人第一次取走k mod (l+1)后，剩下的button是(l+1)的倍数，这时无论第二个人取几个（设他取i个），第一个下一次都可以取(l+1-i)个，使剩下的button也是(l+1)的倍数，这样第一个人一定能拿到最后一个。所以如果k mod (l+1)=0那么第一个人第一次只能取0个，显然是输的。

枚举约数的话，我们从1到sqrt(k)枚举就可以了，但是按题意3<=(l+1),我们会忽略掉2这个约数（如果k是偶数），也同时会忽略掉 k div 2这个约数，最后要特殊判断一下。

program cao;
var
  i,n:longint;
 
begin
  read(n);
  for i:=2 to trunc(sqrt(n))*2 do
    if (n mod (i+1))=0 then
    begin
      writeln(i);
      halt;
    end;
  if odd(n)=false then writeln(n shr 1 -1)
  else writeln(n-1);
end.

---

VAR
  i,n:longint;
BEGIN
  readln(n);
    for i:=3 to n div 2 do
      if n mod i=0 then
        BEGIN
          writeln(i-1);
          halt;
        END;
  writeln(n-1);
END.
//by lzoi_ys

//小改进，只是个小改进，减少了点穷举次数
var i,n:longint;
begin
  readln(n);
  for i:=3 to trunc(sqrt(n))+2 do
    if n mod i=0 then
      begin
        writeln(i-1);
        halt;
      end;
  if not odd(n) then writeln(n shr 1-1)
  else writeln(n-1);
end.

其实只要最后判断ans是否小于2就可以了，少枚举几次……
贴个cpp代码

#include <cstdio>
 
int n,ans;
 
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
 
	scanf("%d",&n);
	for (int i=3;i*i<=n;i++)
	if (n%i==0){
		ans=i-1;
		break;
	}
	if (!ans)
		if(n&1)	ans=n-1;
		else	ans=n/2-1;
	if (ans<2)	ans=n-1;
	printf("%d\n",ans);
 
	return 0;
}