2014-01-14

HDU 4715 Difference Between Primes——素数筛选，二分查找(STL)

这是HDU 4715 Difference Between Primes。由于这几天HDU有些问题，我这里打不开网页，所以我也就不贴链接了。

题目大意是说：对于每个偶数x，都能找到一个两个素数a b，使得a-b=x。

让你验证这个结论，给出x，求出a和b。（x≤1000000）

方法很简单，就是先打个素数表，对于每个给定的数，枚举小的数，二分查找大数即可。

这篇文章中的素数筛选法参考了kuangbin大神和shu_mj的写法，这是一个十分神奇的筛选法。在筛选过程中，每个非质数平均只被访问标记一次，所以效率非常高。

关于题目中的“如果不能查找到则输出FAIL”。其实可以证明，这种情况是不可能出现的。我们把这个程序运行一遍，遍历1~1000000间的所有偶数，都没有出现一个FAIL。所以代码里边这部分内容就略过了。

关于STL的binary_search和lower_bound两者的实现都是二分查找，但是lower_bound会返回一个迭代器，告诉你找到的位置，而binary_serach是返回一个布尔型告诉你有没有找到。

这两种方法一般来说有着不同的作用。这里显然是用binary_serach更好一些。

今天还发现binary_serach有着更为强大的功能：一般来说，binary_serach要求随机访问迭代器，可是在一些没有随机访问迭代器的数据结构上，比如map和list，binary_serach将自动降级为线性搜索算法完成搜索。（←，可见STL确实强大。。。。）

以下为AC代码：

#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 

vector<int> getPrime(int n) { 
    vector<int> prime; 
    bool *vis=new bool[n](); 
    for(int i=2;i<n;i++){ 
        if(!vis[i]) 
            prime.push_back(i); 
        for(int j=0;j<prime.size();j++) { 
            if(i*prime[j]>=n) break; 
            vis[i*prime[j]]=true; 
            if(i%prime[j]==0) break; 
        } 
    } 
    return prime; 
} 
int main(int agrc, char *agrv[]) { 
    vector<int> prime=getPrime(20000000); 

    int caseNum; 
    cin>>caseNum; 
    while(caseNum--){ 
        int x; 
        cin>>x; 

        bool sign; 
        if(x>=0) sign=true; 
        else sign=false,x=-x; 

        int a,b; 
        for(int i=0;i<prime.size();i++){ 
            b=prime[i]; 
            a=b+x; 
            if(binary_search(prime.begin(),prime.end(),a)){ 
                sign&&(cout<<a<<" "<<b<<endl)(cout<<b<<" "<<a<<endl); 
                break; 
            } 
        } 
    } 
} 

main