Codeforces #280 Div2 E. Vanya and Field

Dより簡単。
http://codeforces.com/contest/492/problem/E

問題

N*Nの２次元グリッドがある。
そのうち、座標(X[i],Y[i])が表すM個のセルにリンゴがある。

プレイヤーは任意のグリッド(x,y)から始め、1秒毎に((x+dx)%N,(y+dy)%N)に移動する、ということを繰り返し、リンゴがあるセルを経由するとその場所のリンゴを回収する。
開始位置を適切に選択し、回収できるリンゴを最大化せよ。

なお、xとN、yとNは互いに素である。

解法

条件より、以下のことがわかる。

• N秒毎に到達するセルがループする。
• ループはN通り。
• N秒の間に各X座標、Y座標を1回ずつ通る。

よって各リンゴのあるセルに対し、そこを通るループを代表するセルとしてX座標が0のものを求め、そのY座標ごとにリンゴの数をカウント知ればよい。

各リンゴの座標に対し、X座標が0となる位置を求めるには、Y座標の逆元を求める必要がある。
これはフェルマーの小定理で求めても良いし、前処理で列挙してもよい。

ll N,M,DX,DY;
ll X[1001000],Y[1001000];
int rev[1001000];
int num[1001000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>DX>>DY;
	FOR(i,N) rev[DX*i%N]=i;
	
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		num[((Y[i]-DY*rev[X[i]])%N+N)%N]++;
	}
	x=0;
	FOR(i,N) if(num[i]>num[x]) x=i;
	_P("%d %d\n",0,x);
}

まとめ

これC位でいいと思うんだけどな。
もしくは互いに素の条件を外すか。