有参加 第五届“图灵杯”NEUQ-ACM 程序设计大赛（个人赛）网络同步赛 的吗? ACMClub.cn 的程序是不是有问题啊?

[CEBBCAT]

举例来讲,第一题是:

1855: 逃出生天

题目描述：
gold 学长从昏迷中醒来以后发现自己被困在一个山洞里，他找了很久，终于找到一个门。门上写着：想要逃出去，只有一个办法 你可以选择一个数 n，设 m=1 * 2 * ... * (n-1)。如果 m 是 n 的倍数，那么门就会自动打开，否则你就别想出去了。gold 学长内心充满了绝望，他想了一些数，但他不知道这些数能不能保证自己逃出去。你能帮助 gold 学长逃出生天吗？
输入：
第一行一个数 T （ T<=1000 ），表示 gold 学长想的数的个数 接下来每一行一个数 n （ 2<=n<=1e8 ），表示 gold 学长想的数
输出：
每行一个输出 对于每一个数，如果学长能逃出去，则输出“ escape ”（不含引号），否则输出“ trapped ”（不含引号）

我的代码是:

#include <stdio.h>
int main()
{
	int shuru[1000] = { 0 };
	int shuru_len = 0;
	char pass[7] = "escape";
	char non_pass[8] = "trapped";
	int flag = 0;

	scanf("%d", &shuru_len);

	for (int i = 0; i < shuru_len; i++)
		scanf("%d", &shuru[i]);

	for (int i = 0; i < shuru_len; i++) {
		flag = 0;
		if (!(shuru[i] & 1)) {
			flag = 1;
		} else {
			for (int i = 3; i < shuru[i] / 2; i += 2) {
				if (shuru[i] % i == 0) {
					flag = 1;
				}
			}
		}
		if (flag)
			printf("%s\n", pass);
		else
			printf("%s\n", non_pass);
	}
	return 0;
}

这代码应该没问题吧?

编译提示了 编译错误

可我在本地使用 gcc ./escape.c -o escape -std=c99编译顺利通过, 使用测试数据[4, 5 6 7 8]也输出了应有的结果, gcc --version 输出的是:

➜  ~ gcc --version
gcc (Raspbian 4.9.2-10) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

uname -a 执行结果为:

Linux RaspberryPi-2B 4.9.65-v7+ #1056 SMP Fri Nov 24 13:58:07 GMT 2017 armv7l GNU/Linux

请大家帮忙看看是怎么回事, 多谢啦

[ayyll]

貌似求约数也可以，如果 m % n == 0 那么 n 至少要有两个以上的约数(除了 1 和本身)，而求约数的复杂度是 O(sqrt(n)) 总复杂度为 T * O(sqrt(n))

[tigerstudent]

试试选 c++去提交。会不会是 for 循环里的 int 定义不能放里面？

[wwqgtxx]

你确定人家说了可以用 C99 语法了么

[CEBBCAT]

@ayyll #1 您的意思是说假如 n 有两个因数那 n 即为合乎要求的数字吗?我也是这样想的呢;可能是我代码太抽象, 哈哈

如果(n 为偶数)
n 肯定存在另一个因子,使这个因子与 2 乘积为 n, 这二者会使(n-1)!是 n 的整数倍
如果(n 为奇数, 且在 3~n-1 的范围内有因数,那么 n 同样合乎题意,不再证明)

[CEBBCAT]

@tigerstudent #2
@wwqgtxx #3

谢谢两位的提醒, 我看过了, 只写了内存与时间的限制, 并没有说明对应语言的编译程序与编译选项, 但我稍微修改过代码是可以编译的, 只是不能 100%通过, 所以应该不是标准的事

[leewangyang]

@CEBBCAT 这题本质就是判断素数呗，要用筛法才能全过。

编译问题的话，他们之前说的应该没错，c89 for 里面不能直接 int，我们学校 oj 就不说，但是默认 c89，最好交的时候直接选 c++

[CEBBCAT]

@leewangyang #6
好像你的解法更接近出题着的意愿, 可是我没看明白; 我提交是用了 C++ 的

[leewangyang]

@CEBBCAT m=(n-1)的阶乘，考虑如果 n 是一个质数，m 不可能是 n 的倍数是吧，n 是一个合数，那么 n=k*j （ kj 是两个质因子，而且 kj 均小于 n ）也就是说 m=k*j*(其他剩下的)，所以 m 一定是 n 的倍数

[CEBBCAT]

是四楼里那样的吗?我也是把 m 分拆为 m = n * other 的

[leewangyang]

@CEBBCAT 噢噢噢，你在那楼的分析已经差不多了，可以推出这题就是找质数问题了
但是后来我想了一下有一点小问题，刚才的分析忘记考虑 kj 相等的情况（也就是 n 是完全平方数），如果 kj 相等，m=k*（除了 k 的部分）这个时候就要考虑 k 是否是质数，是质数则 m 不是 n 倍数（比如 n=4 或者 n=49 时候 m 不是 n 的倍数），不是质数则 n 是 m 倍数（比如 n=16 或者 n=81 ），所以你分析的里面对于偶数一定有 2*n （ n=4 是反例），奇数的时候，如果不是完全平方数，则判断 n 是否是质数，如果是完全平方数，则判断平方根是否是质数。。。。手机码字，见谅

[leewangyang]

@CEBBCAT 刚才理论有点乱

结论是，偶数 2 4 不满足
奇数，质数不满足，质数的完全平方数不满足

逻辑：
1. 判断奇偶，偶数判断是否是 2 4，奇数进入 2
2. 判断是否是完全平方数，完全平方数判断平方根是否是质数，不是完全平方数进入 3
3. 判断是否是质数

判断质数最好用筛法

[CEBBCAT]

@leewangyang #10 这次可真是 哇!(Wrong Answer)了, 没想到 4 = 2 * 2 这种情况, 多谢指教啦

[CEBBCAT]

@leewangyang #11 嗯嗯,好的,我再想想为什么 n 为质数时不可能合乎题意

[ayyll]

@CEBBCAT 是滴 我有点傻了 竟然忘了素数的概念了。。 这题本质就是判断 n 是否是素数 ， 判断素数的算法多的是，随便搞就可以了 看你的代码是除到了 n/2，其实到根号 n 就可以了。。不明白可以百度体会下其中的奥妙

[ayyll]

额 大概是我 1L 说的思路，判断约数比较直观
代码 ： http://paste.ubuntu.com/26124159/
我注册试了一下可以过的~

[CEBBCAT]

@ayyll 对呀对呀，现在想明白了，就是判断素数。但我觉得除到 n/2 的理由是……觉得开平方太费时间了，多引入一个库也挺讨厌的……

好吧，其实我是心存侥幸的啦，确实是到平方根比较好😅