http://acm.hdu.edu.cn/showproblem.php?pid=4715
【code】：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath> using namespace std;
#define N 1000151 int prim[N+];
int hash[];
int mark[];
int cjsb[];
int hash_cnt=;
int lowbit(int i)
{
return i&-i;
}
void add(int i,int a)
{
while(i<=N)
{
cjsb[i]+=a;
i+=lowbit(i);
}
}
int sum(int i)
{
int s=;
while(i>)
{
s+=cjsb[i];
i-=lowbit(i);
}
return s;
}
int main()
{
int i,j;
hash_cnt=;
for(i=;i<=N;i++)
{
if(!prim[i])
{
hash[hash_cnt++]=i;
for(j=;j*i<=N;j++)
{
prim[j*i]=;
}
}
}
// cout<<hash_cnt<<" "<<hash[hash_cnt-1]<<endl;
int tou=;
memset(cjsb,,sizeof(cjsb));
for(i=;i<hash_cnt;i++)
{
for(j=;j<=i-;j++)
{
int temp = hash[i]-hash[j];
if(temp<=tou)
break;
if(mark[temp]) continue;
else
{
mark[temp] = hash[i];
add(temp,);
if(sum(temp)==temp/)
tou=temp;
}
}
}
int n;
scanf("%d",&n);
while(n--)
{
int m;
scanf("%d",&m);
if(m==)
{
puts("2 2");
continue;
}
if(m<)
{
m=-m;
printf("%d %d\n",mark[m]-m,mark[m]);
}
else
{
printf("%d %d\n",mark[m],mark[m]-m);
}
}
return ;
}