hdu-7141 Ball （bitset）

Portal ：Problem - 7141

The question ： stay m*m There are... On my chessboard n A little bit , Ask how many options you have Choose three points each time and find the Manhattan distance between two Make the median Manhattan distance a prime number .

analysis ： Obviously, the Manhattan distance between any two points can be preprocessed , Then, when enumerating the prime Manhattan distance, try how many third-party points satisfy the condition . Originally thought it was similar to matrix counting points , But the Manhattan distance around a point is irregular , Besides, there are two points , We need some special treatment . Consider sorting Manhattan distances and then using bitset,dp[i][k]=1 Indication point k To i The distance of is less than the current distance , Add... Every time (dp[a]^dp[b]).count() that will do .

Code ：
 

#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define int __int128
#define pii pair<int,int>
#define endl '\n'// Interactive questions need endl Refresh //
const int maxn=1e6+5;

const int N=1e7;
int flag[N+10];//flag[i]=0 i Prime number  
int prime[N+10];
int cnt;

void init()
{
    flag[0]=1,flag[1]=1;//0 and 1 Not prime 
    for(int i=2;i<=N;i++)
    {
        if(flag[i]==0) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=N;j++)
        {
            flag[i*prime[j]]=1;
            if(i%prime[j]==0) break;// According to the unique decomposition theorem , Each number is only in prime[j] Is its minimum factor when marked (12=2*6!=4*3)
        }
    }
}

int x[2005],y[2005];
bitset<2005>dp[2005];

struct node
{
    int a,b,dis;
}e[2005*2005];

int cal(int a,int b)
{
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}

bool cmp(node c,node d)
{
    return c.dis<d.dis;
}

void solve()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++) dp[i].reset();

    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    int ct=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            e[++ct]={i,j,cal(i,j)};
        }
    }

    sort(e+1,e+ct+1,cmp);

    int ans=0;
    for(int i=1;i<=ct;i++)
    {
        int a=e[i].a,b=e[i].b,dis=e[i].dis;
        if(!flag[dis]) ans+=(dp[a]^dp[b]).count();
        dp[a][b]=dp[b][a]=1;
    }
    cout<<ans<<endl;
}
 
signed main()
{
    init();
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}