举例来讲,第一题是:
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
请大家帮忙看看是怎么回事, 多谢啦
1
ayyll 2017-12-03 18:24:23 +08:00 1
貌似求约数也可以,如果 m % n == 0 那么 n 至少要有两个以上的约数(除了 1 和本身),而求约数的复杂度是 O(sqrt(n)) 总复杂度为 T * O(sqrt(n))
|
2
tigerstudent 2017-12-03 18:33:32 +08:00 2
试试选 c++去提交。会不会是 for 循环里的 int 定义不能放里面?
|
3
wwqgtxx 2017-12-03 18:33:39 +08:00 1
你确定人家说了可以用 C99 语法了么
|
4
CEBBCAT OP @ayyll #1 您的意思是说假如 n 有两个因数那 n 即为合乎要求的数字吗?我也是这样想的呢;可能是我代码太抽象, 哈哈
如果(n 为偶数) n 肯定存在另一个因子,使这个因子与 2 乘积为 n, 这二者会使(n-1)!是 n 的整数倍 如果(n 为奇数, 且在 3~n-1 的范围内有因数,那么 n 同样合乎题意,不再证明) |
5
CEBBCAT OP @tigerstudent #2
@wwqgtxx #3 谢谢两位的提醒, 我看过了, 只写了内存与时间的限制, 并没有说明对应语言的编译程序与编译选项, 但我稍微修改过代码是可以编译的, 只是不能 100%通过, 所以应该不是标准的事 |
6
leewangyang 2017-12-03 21:57:06 +08:00 via Android 1
@CEBBCAT 这题本质就是判断素数呗,要用筛法才能全过。
编译问题的话,他们之前说的应该没错,c89 for 里面不能直接 int,我们学校 oj 就不说,但是默认 c89,最好交的时候直接选 c++ |
7
CEBBCAT OP @leewangyang #6
好像你的解法更接近出题着的意愿, 可是我没看明白; 我提交是用了 C++ 的 |
8
leewangyang 2017-12-03 22:18:06 +08:00 via Android
@CEBBCAT m=(n-1)的阶乘,考虑如果 n 是一个质数,m 不可能是 n 的倍数是吧,n 是一个合数,那么 n=k*j ( kj 是两个质因子,而且 kj 均小于 n )也就是说 m=k*j*(其他剩下的),所以 m 一定是 n 的倍数
|
9
CEBBCAT OP 是四楼里那样的吗?我也是把 m 分拆为 m = n * other 的
|
10
leewangyang 2017-12-03 22:46:40 +08:00 via Android
@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 是否是质数,如果是完全平方数,则判断平方根是否是质数。。。。手机码字,见谅 |
11
leewangyang 2017-12-03 22:51:44 +08:00 via Android
@CEBBCAT 刚才理论有点乱
结论是,偶数 2 4 不满足 奇数,质数不满足,质数的完全平方数不满足 逻辑: 1. 判断奇偶,偶数判断是否是 2 4,奇数进入 2 2. 判断是否是完全平方数,完全平方数判断平方根是否是质数,不是完全平方数进入 3 3. 判断是否是质数 判断质数最好用筛法 |
12
CEBBCAT OP @leewangyang #10 这次可真是 哇!(Wrong Answer)了, 没想到 4 = 2 * 2 这种情况, 多谢指教啦
|
13
CEBBCAT OP @leewangyang #11 嗯嗯,好的,我再想想为什么 n 为质数时不可能合乎题意
|
14
ayyll 2017-12-06 17:36:09 +08:00
@CEBBCAT 是滴 我有点傻了 竟然忘了素数的概念了。。 这题本质就是判断 n 是否是素数 , 判断素数的算法多的是,随便搞就可以了 看你的代码是除到了 n/2,其实到根号 n 就可以了。。不明白可以百度体会下其中的奥妙
|
15
ayyll 2017-12-06 18:28:39 +08:00
|