問題はこちら
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