CF492E题解

屑题。

考虑对于每一个 $(x,y)$，将其与 $((x+dx) \mod n,(y+dy) \mod n)$ 连边。

答案就是连通块中权值最大的那个。

考虑对于 $(x_1,y_1)$ 和 $(x_2,y_2)$ 两个点在同一个连通块中的条件。

条件就是同余方程 $x_1+x * dx \equiv x_2 \bmod n $ 和 $ y_1+y * dy \equiv y_2 \bmod n$ 的解是同一个。

考虑化简：

\[x \equiv \frac {x_2-x_1} {dx} \mod n
\]

\[x \equiv \frac {y_2-y_1} {dy} \mod n
\]

也就是：

\[\frac {x_2-x_1} {dx} \mod n \equiv \frac {y_2-y_1} {dy} \mod n
\]

\[\frac {y_1} {dy} -\frac {x_1} {dx} \equiv \frac {y_2} {dy} - \frac {x_2} {dx} \bmod n
\]

因为值域只有 $O(n)$，开个桶统计一下数量就好了。

因为 $\gcd(n,dx)=\gcd(n,dy)=1$，所以 $dx$ 和 $dy$ 的逆元可以使用 exgcd 计算。

#include<cstdio>

typedef unsigned uint;

const uint M=1e6;

uint n,m,id,dx,dy,x[M],y[M],sum[M];

void exgcd(const uint&a,const uint&b,uint&x,uint&y){

    if(!b)return void((x=1,y=0));exgcd(b,a%b,y,x);y-=a/b*x;

}

inline uint Del(const uint&a,const uint&b){

	return b>a?a-b+n:a-b;

}

signed main(){

	register uint i,T,X,Y;

	scanf("%u%u%u%u",&n,&m,&dx,&dy);

	exgcd(dx,n,X,Y);dx=(X+n)%n;

	exgcd(dy,n,X,Y);dy=(X+n)%n;

	for(i=1;i<=m;++i){

		scanf("%u%u",&X,&Y);

		T=Del(1ull*X*dx%n,1ull*Y*dy%n);

		if(!sum[T])x[T]=X,y[T]=Y;

		if(++sum[T]>sum[id])id=T;

	}

	printf("%u %u",x[id],y[id]);

}

巴特西

CF492E题解

最新文章

热门文章