高分求一道ACM题~!

其实这题应该很简单， 算法中心思想就是找循环节

1. 先说结论，结论就是，狐狸每次找的洞编号形成一个序列，这个序列存在一个循环节，并且循环节的长度不超过n^2

2. 证明这个结论: 设狐狸当前所在洞编号是x，下一洞编号y, 很显然，x和y的范围都是1-n, 那么我们就可以这么想，x和y所有的组合都不超过n^2种，对吧？这个好想吧？比如n = 3, xy分别可以取值11, 12, 13, 21, 22, 23, 31, 32, 33,总共9种。那么很显然，当序列中，所有xy的组合都出现过一次之后，必然会在某个地方重复出现xy(类似于鸽笼原理的意思), 而只要出现了xy, 这个循环节就出现了，因为从x推到y，然后从y再往后推，计算出来的洞编号，肯定是固定的（因为x加了一个数t，变成y，然后y必然是加上数t+1的, 之后的数字必然是y+t+1）

3. 有了这个结论， 就好说了，把狐狸进过的洞都列出来，只需要列出2*n*n个，再往后就不必列举了，就可以得到狐狸所有能进的洞， 然后答案就出来了

4. 解释一下为啥是2*n*n而不是n*n, 因为循环节有这样一个性质，在进入循环节之前，有一个循环头存在，循环头跟循环节不一样，而它的长度不会超过循环节长度，所以我们往后找2*n*n次，这样就可以了

5. 当然，如果你觉得结论不保险，可以多找几次，干脆就往后找个1千万次，肯定是把所有能进的洞都列举出来了。

如果有地方没有解释清楚，可以给我留言

其实代码再简单不过了，如下（编译运行环境dev-c++，测试样例通过）：

main()
{
int cn, i, pre, n, m;
char x[1003];
scanf("%d", &cn);
while (cn--)
{
scanf("%d", &n), m = (n+1)*(n+1)*2;
memset(x, 0, sizeof x);
for (i=0, pre=0; i pre += i%n, pre %= n, x[pre] = 1;
for (i=0, pre=0; i if (!x[i])
if (!pre) printf("%d", i), pre = 1;
else printf(" %d", i);
if (!pre) printf("no safe caves");
printf("\n");
}
}

按c的习惯， 把洞编号0 到n-1。 第一次找0， 然后找1， 然后找3， 然后找6.。。 第i次找的是 i(i-1)/2 % n

有这个就可以算哪个洞要被找了。 要想知道哪个洞安全，还得知道啥时候这个循环能绕回来， 到这时候剩下的洞就算安全了

看看两次找的洞的差： s(s-1)/2 - t(t-1)/2 = (s-t)(s+t-1)/2 = (s-t)[(s-t)+(2t-1) ] /2
所以如果n是偶数 s-t是n的倍数的时候差是 n/2的奇数倍， 不是n的倍数， 所以需要 s-t是2n的倍数的时候才行
如果n是奇数， 那么s-t是n的倍数就能保证这个差是n的倍数了

所以对n是偶数的情况， 要算 2n次， 对n是奇数的情况要算n次

当然对偶数的情况也可以剪掉一部分， 因为从n到2n这里正好是在前一半的对面， 所以后一半用这么算也可以得到

这样的思路应该差不多了吧。。 没试过不知道

这是哪个网站的题目啊，我做好了想提交试试，看看对不对。求给个网址。

看到数论 自动投降

这个题和杭电上一道题是一样的，不过做了很久都没有AC