题解 P2640 【神秘磁石】

YLWang · 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!