- P,Qがどちらも0の場合はX==0とY==0だけを数えます。
- 簡単のため、P,Qの最大公約数を単位とする座標系に変換します。X,Yが変換できなければ弾きます。
- ここで、各方向に進む回数をa,b,c,dと置くと、
1
2
| (a+b)P+(c+d)Q==X - (1)
(c-d)P+(a-b)Q==Y - (2)
|
- となります。
- α=a+b、β=c+dとおきます。
- αP+βQ==1を満たす(α,β)を拡張ユークリッド互除法で求めます。
- 代表値を(z1,z2)とすると、式(1)を満たすのは、α=z1X+Qn、β=z2X-Pnとなります。
- 式(2)を
(β-2d)P+(α-2b)Q==Yと変形し、αとβを代入して、整理します。2*P*d+2*Q*b==(Q*Q-P*P)*n+z2*X*P+z1*X*Q-Yとなります。
- この不定方程式において、 整数解(d,b)を持つようなnが存在する ことが問題が求める条件となります。
- ここで、上で媒介変数表示により変数を一個減らしたことが効いてきます。
(Q*Q-P*P)*n+z2*X*P+z1*X*Q-Yがgcd(2*P,2*Q)の倍数であることが条件ですので、-(z2*X*P+z1*X*Q-Y)%gcd(Q*Q-P*P,gcd(2*P,2*Q))==0を判定します。- なお、このnを用いてd,bを拡張ユークリッド互除法から求めることで、a,cも求まりますので、原点から何回で目標に到達するかを実際に計算することも可能です。
- プログラムにおいてeとfが可変。abs(a)+abs(b)+abs©+abs(d)が最小となるようなe,fを求めるのもまた一興かと(やってませんが)。
http://yukicoder.me/submissions/65751