题解 P2640 【神秘磁石】

发表于 更新于 阅读次数： Waline：
P2640 【神秘磁石】题解。

来发一个比楼下们快的方法。

本题我用的是筛法，但是。

#我优化了！

具体优化的方法呢，就是楼下们太暴力了，竟然直接暴力！（从1到n）

然而。。。

我有更快的方法！

在筛法打质数表的时候，我不仅保留了bool数组（用来判断），我还开了一个整数数组，存了质数，这样，我就直接用质数表暴力，效率提高到了O(不超过n-k的质数个数)

这样，就可以直接循环质数，效率提高了很多。

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int n,k,a[3000],ps;//n，k为题目中的变量，a数组为质数数组，ps为质数下标
bool s[10005]={1,1},ok=1;//s数组为桶，ok为判断有没有满足条件的质数对的变量
void $(){//财迷心窍的我起了一个函数名……
    for (int i=2;i<10001;i++)//筛法标准做法
    if (!s[i]){//s[i]=1表示不为质数，=0则是
        a[ps++]=i;//把i这个质数存下来
        for (int j=i*2;j<10001;j+=i)s[j]=1;//循环标记
    }
}
int main(){
    $();//预处理
    scanf ("%d%d",&n,&k);
    for (int i=0;a[i]<=n&&a[i]+k<=n;i++)if (!s[a[i]+k])//暴力，符合条件就输出
    ok=!printf ("%d %d\n",a[i],a[i]+k);
    if (ok)printf ("empty");//没有就输出empty
        //不要被题目中“相差为k的质数对”所迷惑，实际上，如果你多判一次a[i]-k，答案会输出两遍。具体为什么，自己想。
    return 0;
}