program Project7;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils;
const
maxn=1000;
var
n,m,i:longint;
v:array[1..maxn,0..maxn]of boolean;
u:array[1..maxn]of boolean;
flag:boolean;
begin
try
{ TODO -oUser -cConsole Main : Insert code here }
fillchar(v,sizeof(v),false);
fillchar(u,sizeof(u),true);
i:=0; m:=0;
readln(n);
while True do
begin
inc(i);
inc(m,i);
if m>=n then m:=m mod n;
if m=0 then m:=n;
if not v[m,(i+1)mod n] then begin
v[m,(i+1)mod n]:=true;
u[m]:=false;
end
else break;
end;
flag:=true;
for i := 1 to n do
if u[i] then begin
writeln(i);
flag:=false;
end;
if flag then writeln(-1);
readln;
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
end.
(用Delphi写的,有些没用的头尾说明可以直接去掉)
不知道你的n有多大,这个是平方级算法,n<1000可解
再研究了一下,补充一个O(n)的算法,n<10E6可解
program Project7;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils;
const
maxn=1000000;
var
n,m,i:longint;
v:array[0..maxn]of boolean;
u:array[1..maxn]of boolean;
flag:boolean;
begin
// while not eof do
try
{ TODO -oUser -cConsole Main : Insert code here }
fillchar(v,sizeof(v),false);
fillchar(u,sizeof(u),true);
u[1]:=false;
i:=0; m:=0;
readln(n);
if n<1 then halt;
while True do
begin
inc(i);
inc(m,i);
if m>=n then m:=m mod n;
if m=0 then m:=n;
if m=1 then
if not v[(i+1)mod n] then begin
v[(i+1)mod n]:=true;
end
else begin break; end
else u[m]:=false;
end;
flag:=true;
for i := 1 to n do
if u[i] then begin
writeln(i);
flag:=false;
end;
if flag then writeln(-1);
readln;
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
end.
两个程序的原理都是找寻环节,第二个优化的原理是发现了循环节必在第一个山洞处出现,所以可以直接抛弃无效的储存空间,同时发现循环节出现的规律:n为奇数时n+1步出现循环节,n为偶数时2n+1步出现循环节,所以可以证明效率是O(n)级别的。
至于为什么会出现这个规律,目前还不清楚。。