AT_utpc2020_l

xujindong_ · 2025-08-06 01:14:25 · 题解

考虑让两维变独立。我们可以对 (X-x_i)^2+(Y-y_i)^2 因式分解。通常这会用到虚数，在模意义下就是 p=299993 的二次剩余。则 (X-x_i)^2+(Y-y_i)^2=(X-x_i+I(Y-y_i))(X-x_i-I(Y-y_i))。这就是说，将原坐标系的每个点映射至 (x+Iy,x-Iy)，两点距离变为坐标差的乘积。

映射后，(X,Y) 仍然取遍 [0,p-1]\times[0,p-1]。对 \prod(X-x_i),\prod(Y-y_i) 开个桶算即可。

#include<bits/stdc++.h>
using namespace std;
const int mod=299993,I=139302;
int n,z,inv[299993],p[299993],q[299993],a[299993],b[299993];
long long ans;
int main(){
  inv[0]=inv[1]=1;
  for(int i=0;i<mod;i++)p[i]=q[i]=1;
  for(int i=2;i<mod;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
  cin>>n>>z;
  for(int i=1,x,y,t;i<=n;i++){
    cin>>x>>y,t=1ll*y*I%mod,y=(x-t+mod)%mod,x=(x+t)%mod;
    for(int j=0;j<mod;j++)p[j]=1ll*p[j]*(j-x+mod)%mod,q[j]=1ll*q[j]*(j-y+mod)%mod;
  }
  for(int i=0;i<mod;i++)a[p[i]]++,b[q[i]]++;
  if(!z)return cout<<1ll*(a[0]+b[0])*mod-1ll*a[0]*b[0]<<'\n',0;
  for(int i=1;i<mod;i++)ans+=1ll*a[i]*b[1ll*z*inv[i]%mod];
  return cout<<ans<<'\n',0;
}