自动搬运

查看原文

来自洛谷，原作者为

	YLWang 别等到一千年以后 所有人都遗忘了我

搬运于2025-08-24 21:39:57，当前版本为作者最后更新于2018-08-23 17:20:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

正常的题解已经够多了，现在我来讲一下打表方法。

打表，是一种极其实用的方法。尤其是打质数表。在不想打 $O(n)$ 素数筛法的时候，可以用打表代替。

对于这道题目，虽然直接暴力也能过，但要是把 $n$ 改为 $1000000$ 暴力就全线崩溃了。只要在 $O(1)$ 时间内判断出某个数是否为质数，就可以轻松过掉如上数据。

其实上面的都是废话

那究竟如何打表呢？

首先，我们要创建一个打表程序，像这样：

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define For(i, j, k) for(int i=(j);i<=(k);i++)
#define INF (2147483647>>1)
using namespace std;
inline int read()
{
    int num=0;
    char c=' ';
    bool flag=1;
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=0;
    for(;c>='0'&&c<='9';num=(num<<1)+(num<<3)+c-48,c=getchar());
    return flag?num:-num;
}
//这是暴力判断
bool pd(int x) {
	if(x == 1 || x == 0) return 0;
	if(x == 2) return 1;
	int g = sqrt(x) + 1;
	For(i, 2, g) {
		if(!(x % i)) {
			return 0;
		}
	}
	return 1;
} 
int main()
{
	//打出来的字符太多，屏幕上存不下QAQ，所以只能输出到文件内
	freopen("stone.txt", "w", stdout);
	For(i, 1, 10000) {//输出每个数
		if(pd(i)) printf("1,");                    
		else printf("0,");
	}
	
	return 0;
}

接下来打开stone.txt。注意：请使用写字板！把这些东西复制下来，存进要提交的代码。

于是最终代码长这样：

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define For(i, j, k) for(int i=(j);i<=(k);i++)
#define INF (2147483647>>1)
using namespace std;
inline int read()
{
    int num=0;
    char c=' ';
    bool flag=1;
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=0;
    for(;c>='0'&&c<='9';num=(num<<1)+(num<<3)+c-48,c=getchar());
    return flag?num:-num;
}
#define N 10005
int p[N] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0...};//省略
int main()
{
	int n = read(), k = read();
	bool flag = 0;
	For(i, 1, n-k) {
		if(p[i] && p[i+k]) {
			printf("%d %d\n", i, i+k);
			flag = 1;
		}
	}
	if(!flag) {
		printf("empty\n");
	}
	return 0;
}

OK!