【NOIP模拟】哥德巴赫矩阵

解析：

       我们观察到题目的本质是求区间中质数的个数，于是就解决了。

 

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;

const int Max=1000010;
int n,q,X1,X2,Y1,Y2,ans;
int vis[Max],sum[Max];

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') {f=-1;c=getchar();}
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}

inline void pre1()
{
	for(int i=2;i<=1000000;i++)
	{
	  if(vis[i]) continue;
	  for(int j=i;j<=1000000/i;j++) vis[i*j]=1;
	}
}

inline void pre2()
{
	for(int i=2;i<=1000000;i++)
	{
	  if(vis[i]) continue;
	  for(int j=i;j<=1000000/i;j++) vis[i*j]=1;
	}
	for(int i=3;i<=1000000;i++) if(!vis[i]) sum[i]=1;
	for(int i=3;i<=1000000;i++) sum[i]+=sum[i-1];
}

int main()
{
	q=get_int();
	if(q<=100)
	{
	  pre1();
	  while(q--)
	  {
	    ans=0;
	    X1=get_int(),Y1=get_int(),X2=get_int(),Y2=get_int();
	    for(int i=X1;i<=X2;i++)
	      for(int j=Y1;j<=Y2;j++)
	        if(!((i+j)%2) &&i!=1 && j!=1 && !vis[i] && !vis[j] && j%2 && i%2) ans++;
	    cout<<ans<<"\n";
 	  }
 	}
 	else
 	{
 	  pre2();
 	  while(q--)
 	  {
	    X1=get_int(),Y1=get_int(),X2=get_int(),Y2=get_int();
	    int num1=sum[X2]-sum[X1-1],num2=sum[Y2]-sum[Y1-1];
	    cout<<(long long)(num1)*(long long)(num2)<<"\n";
 	  }
 	}

	return 0;
}