読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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

問題はこちら
No.321 (P,Q)-サンタと街の子供たち - yukicoder


P,Qが共に0なら自明。そうでないとする

「(a,b)に移動dできるための必要十分条件は、『a,bがd:=GCD(P,Q)の倍数』かつ『【P/d,Q/dの少なくとも一方が偶数】または【a/d+b/dが偶数】』」

実験すれば直感的には明らかだけれど、厳密に証明しようとすると面倒なことになる
場合分けがしつこいようなので、もう少し良い方法があれば教えて下さい

===証明===
d=gcd(P,Q)とおくと、x座標,y座標のmod dは移動前後で変化しないので、x,yが共にdの倍数であることが(x,y)に到達できるための必要条件であることは明らか
よってそのような座標だけ残して全体をdで割ることで、P,Qは互いに素であるとして良い。
P,Qは入れ替えても影響なく、P,Qが共に偶数になることはないので(∵互いに素)Qは奇数して良い

以下に登場する文字は全て整数であるとする(「解を持つ」なども「整数の範囲で」の意味とする)

例えば(-P,-Q)の移動は(P,Q)を-1回したと思うことにすれば
移動は(P,Q),(P,-Q),(Q,P),(Q,-P)のいずれかであり、これらを各x,y,z,w回行って(a,b)に移動できたとすると
(x+y)P+(z+w)Q=a (x座標をみた)
(z-w)P+(x-y)Q=b (y座標をみた)……★
が成立する。よって(a,b)に移動できるための必要十分条件はx,y,z,wに関する連立方程式★が解を持つこと
一般に、連立方程式
x+y=n
x-y=m
が解を持つこととn,mの偶奇が一致することは同値なので
αP+βQ=a
γP+δQ=b
がα≡δ、β≡γ mod2 なる解を持つことが、★が解を持つめための必要十分条件
この条件を使って考える

s,tをsP+tQ=1となるように取り固定する(P,Qは互いに素なので存在)

・(1,0)に到達可能かどうか考える
(case A) Pが偶数の時
sP+tQ=1 なのでmod2で見ればtは奇数なのでsの偶奇によって
sP+tQ=1 と (s+Q)P+(t-P)Q=1 のどちらか一方と
QP+(-P)Q=0 の偶奇が一致する
よって(1,0)へは移動可能。対称性より(-1,0)や(0,1)へも移動可能なので任意の点へ移動可能
(case B) Pが奇数のとき
移動前後で(x座標)+(y座標)の偶奇は変化しないので、原点から(1,0)には到達できない


・Pが奇数のとき(1,1)に到達可能か考える
(case A) s,tの偶奇が一致するとき
sP+tQ=1
sP+tQ=1
より成立
(case B) s,tの偶奇が一致しないとき
sP+tQ=1
(s+Q)P+(t-P)Q=1
となるので成立

対称性より(1,-1)等にも到達可能なので、a+b≡0 mod 2を満たす任意の(a,b)に到達可能であることが分かる


よってまとめると
Pが偶数の時、任意の点に移動可能
Pが奇数の時、a+bが偶数である点(a,b)全てにのみ移動可能

===証明終===

解説を読んでも、「具体的にsP+tQ=aを解いて~~」とやっている方以外は「P,Qが共に奇数だと(1,0)には行けない」しか言ってないくて、「(1,1)にはいつでも行けて、Pが偶数なら(1,0)にも行ける」の証明が書いてなかったので頑張ってやってみたけど、綺麗な証明にならなかった。
(1,1)と(1,0)を調べなくても、まとめて「(a,b)に到達可能か?」だけをみて同じ結論を得ることができるが、その場合a,bの偶奇、s,tの偶奇、P,Qの偶奇で場合分けが大変なことになったので、わかりやすさのために上のような構成にした。

そういうわけでこれをそのまま実装すると次のようになる

int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
	int p,q,d,f,n,x,y,s=0;
	scanf("%d%d%d",&p,&q,&n);
	if(p==0&&q==0){
		while(n--){
			scanf("%d%d",&x,&y);
			if(x==0&&y==0)s++;
		}
	}else{
		d=gcd(p,q);
		if(p/d%2==0||q/d%2==0)f=1;
		else f=0;
		while(n--){
			scanf("%d%d",&x,&y);
			if(x%d==0&&y%d==0&&(f||(x/d+y/d)%2==0))s++;
		}
	}
	printf("%d",s);
	return 0;
}

『【P/d,Q/dの少なくとも一方が偶数】または【a/d+b/dが偶数】』というのは『【P/d,Q/dが共に奇数かつa/d+b/dが奇数】ではない』と書き換えられるので

s,p,q,x,y;
main(f){
	scanf("%d%d%d",&p,&q,&s);
	for(y=p,f=q;x=y;f=x)y=f%x;
	//p,qは破壊出来ないので別変数に渡してから互除法
	//最大公約数はfに入る。「fが0⇔pが0かつqが0」に注意
	for(;~scanf("%d%d",&x,&y);s-=f?x%f|y%f||(x+y)/f&(p+q)/f%2<1:x||y);
	//行けない場所の数を引く
	s=!printf("%d",s);
}

として154B