适当进行骗分是真的有用。
\(40pts\)：
对于每两个点建立一条边，然后在贪心每次求最小边，在期间进行01背包即可，01背包用于处理模数。
设 \(dp_{i,j}\) 代表以 \(i\) 为编号的一个并查集，子集的和模数是否可以为 \(j\)。
每次将 \(t\) 集合合并给 \(i\) 集合。
\(dp_{i,j}|=dp_{t,j}\)
再从 \(1\) 到 \(n\) 枚举 \(k\) 集合中的数 \(p\)。（如果枚举 \(0\) 说明在此已经有答案了，所以枚举 \(0\) 无意义）
\(dp_{i,j}|=dp_{t,(j+p)\bmod k}\)
当合并后 \(dp_{i,0}=1\)，取这条边为答案即可。
非正解做法（这里注重考场上没想出来如何骗分，看正解可以移步其他题解，注：目前这个解法可以过）：
一来想不太出来，但是推出个结论，要推出模数 \(0\)，最多需 \(k\) 个数。
证明：如果一个新的数加进来，不会产生其他模数，那么原来的模数是个等差数列，并且等差数列会从 \(0\) 开始，公差为新数，所以原来取的数都是一样的。如果不会产生模数，那么证明这些相同的数 \(x\) 满足 \(k\bmod x=0\)，那么此时只需要用 \(k\div x\) 即可推出模数 \(0\)，如果可以更新模数每一次更新一个，最多需要 \(k\) 步，若 \(x=1\) 也是 \(k\) 步，即可证。
那么可以想到其实只需要求一个点离的最近的 \(k\) 个点即可。
如果在考场想不到二分什么的，应该考虑揣摩出题人心理，进行关键字排序。
对于每个点 \((x,y)\)：
以 \(x\) 为关键字排序：\(160pts\)。
以 \(y\) 为关键字排序：\(160pts\)
以 \(x^2+y^2\) 为关键字排序：\(160pts\)
以 \(x\times y\) 为关键字排序：\(160pts\)
以 \(x^2+y^2-2x-2y\) 为关键字排序：\(160pts\)
……
好吧当我没说。
这里选择第三种排序，排序后取在自己后面的点，这里因为 \(k\le30\)，所以选择 \(40\) 个点稳一点。
最后与上面做法就一样了，多加了个启发式合并，对于单独一个点的并查集插入进行特殊处理，不用也可以过。
总结：如果考试想不出来，利用一些非正常办法也可以拿高分的。
复杂度 \(O(k\times n\times \log(n))\)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e4+5;
int n,k,cnt,f[N],siz[N],s[N][35],q[N];
struct node
{
int x,y,data;
}a[N];
int cmp(node fi,node se)
{
return fi.x*fi.x+fi.y*fi.y<se.x*se.x+se.y*se.y;
}
struct node2
{
int from,to,data;
}t[N*40];
int cmp2(node2 fi,node2 se)
{
return fi.data<se.data;
}
int afind(int x)
{
if(f[x]==x)return x;
return f[x]=afind(f[x]);
}
int krus()
{
for(int i=1;i<=cnt;i++)
{
int from=afind(t[i].from),to=afind(t[i].to);
if(from==to)continue;
if(siz[to]==1)swap(from,to);
for(int j=1;j<k;j++)q[j]=0;
for(int j=1;j<k;j++)
{
if(!s[to][j])continue;
if(siz[from]==1)q[(j+a[from].data)%k]=1,q[a[from].data]=1;
else
{
for(int p=1;p<k;p++)
{
if(!s[from][p])continue;
q[(j+p)%k]=1;
q[p]=1;
}
}
}
for(int j=0;j<k;j++)s[to][j]|=q[j];
siz[to]+=siz[from];
f[from]=to;
if(s[to][0])return t[i].data;
}
return t[cnt].data;
}
signed main()
{
//freopen("drzava.in","r",stdin);
//freopen("drzava.out","w",stdout);
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].data),a[i].data%=k;
sort(a+1,a+1+n,cmp);
int kt=2000000ll/n;
for(int i=1;i<=n;i++)
{
f[i]=i;
siz[i]=1;
s[i][a[i].data]=1;
for(int j=i+1;j<=min(n,i+kt);j++)t[++cnt]=(node2){i,j,(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)};
}
sort(t+1,t+1+cnt,cmp2);
double ans=sqrt(1.0*krus());
printf("%.3lf",ans);
return 0;
}