SRM401 Div2 250

問題

(x1,y1)と(x2,y2)の2つの点が与えられる．これらを端点とする線分をひいた時に，その線分上の点でx,yどちらも整数座標となる座標がいくつあるか答えよ．ただし，端点は含まない．

考え方

線分のどちらかの端点が原点になるように移動し，線対称にしても整数座標と交差する場所はかわからないので，x=abs(x1-x2),y=abs(y1-y2)とする．
(0,0)から(x,y)にのびてる線分のうちどちらも整数となるものを考えると，0からgcd(x,y)までの数字*なんらかのパラメータでそれぞれのx,yを表現できる．すなわち，gcd(x,y)-1個が答えになる．

参考

蟻本P.118