cf492 E. Vanya and Field（exgcd）

题意：

在 \([0,n)\times [0,n)\) 网格中有m个果子。走任意次，每次能从当前位置 \((x,y)\) 走到 \((x+d_x,y+d_y)\mod n\)。

选择一个起点使能获得的果子数最多。

保证 \(\gcd(n,d_x)=\gcd(n,d_y)=1\)

\(n\le 1e6,m\le 1e5, 1\le d_x,d_y\le n\)

思路：

把 x 变换到0，统计不同 y 的数量，找最多的即可。

把 x 变换到0就是解 \(x+kd_x \equiv 0 \pmod n\implies (-k)d_x+qn=x\)。题目还保证 \(d_x,n\) 互质，那就很方便了

signed main()
{
    cin >> n >> m >> dx >> dy;
    exgcd(dx, n, k, q), k = (n - k) % n; //k=-k
    while(m--)
    {
        cin >> x >> y;
        int yy = (y+k*x%n*dy%n)%n;
        ++cnt[yy];
        if(cnt[yy] > cnt[ansy]) ansy = yy;
    }

    cout << "0 " << ansy;
}