Vanya and Field
题目链接：http://www.codeforces.com/problemset/problem/492/E
逆元
刚看到这题的时候一脸懵逼不知道从哪下手好，于是打表找规律。但是打出来的东西完全不能看啊，有个鬼规律(╯‵□′)╯︵┻━┻，是我数据处理不当？按x排序后发现从一个点出发可以到达任意一个x坐标，回过去看题，发现有这么一句话：The following condition is satisfied for the vector：$gcd(n,dx)=gcd(n,dy)=1$，恩，好像有点思路了。(x,y)的下一个点的坐标是[(x+k*dx)%n,(y+k*dy)%n]也可以写作[(x+k*dx+a*n),(y+k*dy+b*n)],也就是说每个不互相覆盖的(x,y)都唯一对应一个(0,y')，利用扩展欧几里得（如果n是质数可以用费马小定理）计算dx对n的逆元，从而可以求得对应的y'。于是只要处理每个(x,y)，对应的(0,y')个数++，最后找到个数最多的(0,y')就好了。
代码如下：
#include<cstdio>
#define LL long long
using namespace std;
LL k,t;
struct node{
LL sum,x,y;
bool flag;
}times[];
LL query[][];
LL n,m,dx,dy;
LL exGCD(LL a,LL b){
if(b==){
k=;
t=;
return a;
}
LL r=exGCD(b,a%b);
LL tmp=k;
k=t;
t=tmp-(a/b)*t;
return r;
}
int main(void){
LL Max=,Index=;
scanf("%I64d%I64d%I64d%I64d",&n,&m,&dx,&dy);
exGCD(dx,n);
k=(k%n+n)%n;
for(LL i=;i<m;++i){
LL x,y;
scanf("%I64d%I64d",&x,&y);
query[i][]=x,query[i][]=y;
LL temp=y-x*k*dy;
temp = (temp%n + n)%n;
temp%=n;
times[temp].sum++;
if(times[temp].sum>Max){
Max=times[temp].sum;
Index=temp;
}
if(times[temp].flag==){
times[temp].x=x;
times[temp].y=y;
times[temp].flag=;
}
}
printf("%I64d %I64d\n",times[Index].x,times[Index].y);
return ;
}