Vanya and Field

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')就好了。

代码如下：

 1 #include<cstdio>
 2 #define LL long long
 3 using namespace std;
 4 LL k,t;
 5 struct node{
 6     LL sum,x,y;
 7     bool flag;
 8 }times[1000005];
 9 LL query[100005][2];
10 LL n,m,dx,dy;
11 LL exGCD(LL a,LL b){
12     if(b==0){
13         k=1;
14         t=0;
15         return a;
16     }
17     LL r=exGCD(b,a%b);
18     LL tmp=k;
19     k=t;
20     t=tmp-(a/b)*t;
21     return r;
22 }
23 int main(void){
24     LL Max=0,Index=0;
25     scanf("%I64d%I64d%I64d%I64d",&n,&m,&dx,&dy);
26     exGCD(dx,n);
27     k=(k%n+n)%n;
28     for(LL i=0;i<m;++i){
29         LL x,y;
30         scanf("%I64d%I64d",&x,&y);
31         query[i][0]=x,query[i][1]=y;
32         LL temp=y-x*k*dy;
33         temp = (temp%n + n)%n;
34         temp%=n;
35         times[temp].sum++;
36         if(times[temp].sum>Max){
37             Max=times[temp].sum;
38             Index=temp;
39         }
40         if(times[temp].flag==0){
41             times[temp].x=x;
42             times[temp].y=y;
43             times[temp].flag=1;
44         }
45     }
46     printf("%I64d %I64d
",times[Index].x,times[Index].y);
47     return 0;
48 }