yukicoder : No.321 (P,Q)-サンタと街の子供たち

★2.5くらい？
http://yukicoder.me/problems/849

問題

サンタは初期状態で2次元座標の原点にいる。
整数P,Qに対し、サンタは現在位置から相対的に(±P,±Q)または(±Q,±P)の位置の座標に移動出来る。

N個の座標が与えられるので、それぞれ到達可能か判定せよ。

解法

P==0, Q==0の場合は原点から移動できないので自明。
以下それ以外の場合を考える。

拡張ユークリッドの互除法の要領で考えると、X,Y座標それぞれ最小の移動距離はGCD(P,Q)である。
よってN個の点のうちX,Y座標がGCD(P,Q)の倍数でない点はそもそも到達できない。

また、GCD(P,Q)の倍数であっても到達不可能な点もある。
以下座標全体をGCD(P,Q)で割り、P,Qが互いに素であることを前提とする。

P,Qがともに奇数の場合、最小移動距離である(+1,0)には移動できない。(+1,+1)のみの移動になってしまう。
(+1,0)に移動するには、X軸方向で±P,±Qの移動回数が片方奇数、片方偶数でなければならない。
その場合、Y座標の移動距離も奇数になってしまう。
よってP,Qがともに奇数の場合、X,Y座標の偶奇が一致する点にしか移動できない。

ll P,Q;
int N;
ll X[101010],Y[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int ret=0;
	cin>>P>>Q>>N;
	if(P>Q) swap(P,Q);
	
	FOR(i,N) cin>>X[i]>>Y[i];
	if(Q) {
		int g=__gcd(P,Q);
		if(((P/g)+(Q/g))%2) {
			FOR(i,N) if(X[i]%g==0 && Y[i]%g==0) ret++;
		}
		else {
			FOR(i,N) if(X[i]%g==0 && Y[i]%g==0 && abs(X[i]/g+Y[i]/g)%2==0) ret++;
		}
	}
	else {
		FOR(i,N) if(X[i]==0 && Y[i]==0) ret++;
	}
	
	cout<<ret<<endl;
}

まとめ

非常に責任感が強いサンタなら、(P,Q)サンタのまま苦労するより、(1,0)サンタになる努力をするべきじゃないですかねぇ…。